PS(代码打得不好，所以认真写几道ACM的题吧。。数据机构划水全忘了，一点点补吧。)
认真的告诉自己：我是真的菜，多打代码。
zoj1203 最小生成树 kruskal方法
#include "stdafx.h" #include<iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <cstdlib> #include<iomanip> using namespace std; #define MAX 10100 int parent[110]; double x[110], y[110]; double ans = 0.0; int cnt; struct Edge { int u, v; double w; }EG[MAX]; int Find(int x) { return (parent[x] == -1) ? x : Find(parent[x]); } bool cmp(Edge a, Edge b) { return a.w < b.w; } void Kruskal() { ans = 0.0; memset(parent, -1, sizeof(parent)); sort(EG, EG + cnt, cmp);//从最小权值开始考虑 like priority_queue for (int i = 0; i < cnt; i++) { /* 判断任意一条边的两个段顶点是否来自同一个连通分量 即加上了这条边是否形成回路:没有形成回路就加上去 */ int t1 = Find(EG[i].u); int t2 = Find(EG[i].v); if (t1 != t2) { ans += EG[i].w; parent[t1] = t2; } } } int main() { int n,cas=0; while (cin >>n && n!= 0) { for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } cnt = 0;//边的数量 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { EG[cnt].u = i; EG[cnt].v = j; EG[cnt].w = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] -y[j])*(y[i] - y[j])); cnt++; } } Kruskal(); if (cas > 0) cout << endl; cout << "Case #" << ++cas << ":" << endl; cout << "The minimal distance is: " << setiosflags(ios::fixed) << setprecision(2) << ans << endl; } return 0; }
