首页 > 代码库 > uva10034
uva10034
题目链接请戳 这里
解题思路
克鲁斯卡尔求最小生成树
代码
#include<iostream> #include<iomanip> #include<algorithm> #include<cmath> using namespace std; const int N = 110; struct point { double x, y; }V[N]; //边集 struct edge { double w; int u, v; }e[N*N]; int d[N*N]; //存储每条边的编号,用来间接排序 int set[N]; //并查集 int n; double get_lenth(point a, point b) { double lenth; lenth = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); return lenth; } int cmp(const int i, const int j) { return e[i].w < e[j].w; } void make_set() { for (int i = 1; i <= n; i++) { set[i] = i; } } int find(int x) { return set[x] == x ? x : set[x] = find(set[x]); } double Kru(int m) { double ans = 0; for (int i = 0; i < m; i++) { int t = d[i]; int fa = find(e[t].u); int fb = find(e[t].v); if (fa != fb) { set[fa] = fb; ans += e[t].w; } } return ans; } int main() { int tests; cin >> tests; while (tests--) { int size = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> V[i].x >> V[i].y; } //建图,每对顶点之间都有一条边 for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) if (i != j) { int x = size; e[x].w = get_lenth(V[i], V[j]); e[x].u = i; e[x].v = j; d[x] = x; size++; } } //初始化并查集 make_set(); //对边集排序 sort(d, d + size, cmp); //输出结果,保留小数点后两位数字 cout.flags(ios::fixed); cout << setprecision(2) << Kru(size) << endl; if (tests) cout << endl; } }
uva10034
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。