poj1251:http://poj.org/problem?id=1251
题意：求n个村庄之间的最小生成树。
题解：建好图，然后之间kruska直接解题。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int n,num,k,cnt,sum,tt,next1; 7 char s1,s2; 8 int pa[28]; 9 struct Node{ 10 int u; 11 int v; 12 int w; 13 bool operator<(const Node &a)const{ 14 return w<a.w; 15 } 16 }edge[1000]; 17 void UFset(){//初始化 18 for(int i=1;i<=n;i++) 19 pa[i]=-1; 20 } 21 int Find(int x){//查找 22 int s; 23 for(s=x;pa[s]>=0;s=pa[s]); 24 while(s!=x){ 25 int temp=pa[x]; 26 pa[x]=s; 27 x=temp; 28 } 29 return s; 30 } 31 void Union(int R1,int R2){//合并 32 int r1=Find(R1); 33 int r2=Find(R2); 34 int temp=pa[r1]+pa[r2]; 35 if(pa[r1]>pa[r2]){ 36 pa[r1]=r2; 37 pa[r2]=temp; 38 } 39 else{ 40 pa[r2]=r1; 41 pa[r1]=temp; 42 } 43 } 44 void kruska(){//求最小生成树 45 UFset(); 46 num=0;sum=0; 47 for(int i=1;i<cnt;i++){ 48 int u=edge[i].u; 49 int v=edge[i].v; 50 if(Find(u)!=Find(v)){ 51 num++; 52 sum+=edge[i].w; 53 Union(u,v); 54 } 55 if(num>=n-1)break; 56 } 57 printf("%d ",sum); 58 } 59 int main(){ 60 while(~scanf("%d",&n)&&n){ 61 cnt=1; 62 for(int i=1;i<n;i++){ 63 //scanf("%c%d",s1,&tt);//注意 %c会把空格也会读进去 64 cin>>s1>>tt; 65 for(int j=1;j<=tt;j++){//建图 66 //scanf("%c %d",s2,&next1); 67 cin>>s2>>next1; 68 edge[cnt].u=s1-'A'+1; 69 edge[cnt].v=s2-'A'+1; 70 edge[cnt++].w=next1; 71 } 72 } 73 sort(edge+1,edge+cnt);//排序 74 kruska(); 75 76 } 77 }