HDU 1233 还是畅通工程
http://acm.hdu.edu.cn/showproblem.php?pid=1233
题意：
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
思路：
我用了Kruskal算法。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn = 5000 + 5; 7 8 int n, ans; 9 int p[maxn]; 10 11 struct node 12 { 13 int u; 14 int v; 15 int w; 16 }edge[maxn]; 17 18 int find(int x) 19 { 20 return p[x] == x ? x : find(p[x]); 21 } 22 23 bool cmp(node a, node b) 24 { 25 return a.w < b.w; 26 } 27 28 void Kruskal() 29 { 30 int cnt = n*(n - 1) / 2; 31 sort(edge, edge + cnt, cmp); 32 for (int i = 0; i < cnt; i++) 33 { 34 int x = find(edge[i].u); 35 int y = find(edge[i].v); 36 if (x != y) 37 { 38 p[x] = y; 39 ans += edge[i].w; 40 } 41 } 42 } 43 44 int main() 45 { 46 //freopen("D:\txt.txt", "r", stdin); 47 while (scanf("%d",&n) && n) 48 { 49 for (int i = 1; i <= n; i++) 50 p[i] = i; 51 for (int i = 0; i < n*(n - 1) / 2; i++) 52 { 53 scanf("%d%d%d", &edge[i].u, &edge[i].v , &edge[i].w); 54 } 55 ans = 0; 56 Kruskal(); 57 printf("%d ",ans); 58 } 59 return 0; 60 }