首页 > 代码库 > UVA 10397 Connect the Campus
UVA 10397 Connect the Campus
MST 比较水。给出的M个直接合并就好。边权就还是DIST;
或者直接M个点对的边权直接设置为0
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 755int p[MAXN];int N,M,cas;int Find(int x) {return x == p[x] ? x : p[x] = Find(p[x]);}struct node{ int x,y;}src[MAXN];struct dis{ int u,v; double dist; friend bool operator < (const dis &a,const dis &b) { return a.dist < b.dist; }}d[MAXN*MAXN];void read(){ cas = 0; for (int i = 1; i <= N; i++) scanf("%d%d",&src[i].x,&src[i].y); for (int i = 1; i <= N; i++) for (int j = i + 1; j <= N; j++) { d[cas].u = i; d[cas].v = j; d[cas++].dist = sqrt((double)((src[j].x - src[i].x) * (src[j].x - src[i].x)) + (double)((src[j].y - src[i].y) * (src[j].y - src[i].y))); } sort(d,d + cas); scanf("%d",&M); for (int i = 0; i <= N; i++) p[i] = i; while (M--) { int u,v; scanf("%d%d",&u,&v); int x = Find(u) , y = Find(v); if (x != y) p[x] = y; }}double kruskal(){ double ans = 0; for (int i = 0; i < cas; i++) { int u = d[i].u , v = d[i].v ; double w = d[i].dist; int x = Find(u) , y = Find(v); if (x != y) { ans += w; p[x] = y; } } return ans;}int main(){ while (scanf("%d",&N) != EOF) { read(); printf("%.2lf\n",kruskal()); } return 0;}
UVA 10397 Connect the Campus
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。