HDU 1863 畅通工程（kruskal算法）
转载请注明出处：http://blog.csdn.net/a1dark
分析：还是一道水水的最小生成树、改了一点条件而已、代码基本不变、继续水、
#include<stdio.h>#include<algorithm>using namespace std;struct node{ int s,e; int val;}flag[150];int map[150];int n,m,temp;int cmp(node a,node b){ if(a.val<b.val) return 1; else return 0;}void init(){ for(int i=1;i<=m;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; temp--; return 1; } return 0;}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ if(n==0)break; for(int i=0;i<n;i++){ scanf("%d%d%d",&flag[i].s,&flag[i].e,&flag[i].val); } sort(flag,flag+n,cmp); int sum=0,ans=0; temp=m-1; init(); for(int i=0;i<n;i++){ ans=merge(flag[i].s,flag[i].e); if(ans) sum+=flag[i].val; } if(temp>0) printf("?\n"); else printf("%d\n",sum); } return 0;}