HDU 1233 还是畅通工程
转载请注明出处：http://blog.csdn.net/a1dark
分析：kruskal模板算法、原理很简单、就是先把边从小到大排个序、然后并查集、并在一起就OK、
#include<stdio.h>#include<algorithm>using namespace std;struct node{ int s,e; int val;}flag[5050];int map[5050];int n;int cmp(node a,node b){ if(a.val<b.val) return 1; else return 0;}void init(){ for(int i=1;i<=n*(n-1)/2;i++) map[i]=i;}int find(int x){ int r=x; while(r!=map[r]) r=map[r]; int b=x; int f; while(b!=r){ f=map[b]; map[b]=r; b=f; } return r;}int merge(int x,int y){ int fx=find(x); int fy=find(y); if(fx!=fy){ map[fx]=fy; return 1; } return 0;}int main(){ while(scanf("%d",&n)!=EOF){ if(n==0)break; for(int i=0;i<n*(n-1)/2;i++){ scanf("%d%d%d",&flag[i].s,&flag[i].e,&flag[i].val); } sort(flag,flag+(n*(n-1)/2),cmp); int sum=0,ans=0; init(); for(int i=0;i<n*(n-1)/2;i++){ ans=merge(flag[i].s,flag[i].e); if(ans) sum+=flag[i].val; } printf("%d\n",sum); } return 0;}