http://acm.hdu.edu.cn/showproblem.php?pid=1301
最小生成树模板题
1 #include<iostream> 2 #include<stdio.h> 3 #include<math.h> 4 #include<string.h> 5 #include<stdlib.h> 6 using namespace std; 7 const int N=600; 8 struct stu{ 9 int u; 10 int v; 11 int w; 12 }p[N]; 13 int k,t; 14 int father[N]; 15 int cmp(const void *a,const void *b) 16 { 17 return (*(struct stu*)a).w > (*(struct stu*)b).w ?1:-1; 18 } 19 int find(int x) 20 { 21 if(father[x]!=x) 22 father[x]=find(father[x]); 23 return father[x]; 24 } 25 int make(int a,int b) 26 { 27 int h=0; 28 int f1=find(a); 29 int f2=find(b); 30 if(f1>f2) 31 { 32 father[f2]=f1; 33 h=1; 34 } 35 else if(f1<f2) 36 { 37 father[f1]=f2; 38 h=1; 39 } 40 return h; 41 } 42 int kruskal() 43 { 44 int h=0; 45 int s=0; 46 for(int i=0;i<k;i++) 47 { 48 if(make(p[i].u,p[i].v)) 49 { 50 h++; 51 s+=p[i].w; 52 } 53 if(h==t-1) 54 return s; 55 } 56 return s; 57 } 58 59 60 int main() 61 { 62 //freopen("in.txt","r",stdin); 63 int n,m; 64 char a,c; 65 while(~scanf("%d",&t)) 66 { 67 if(!t) 68 break; 69 for(int i=1;i<=t;i++)//刚开始t的位置我写的是常量N，就是过不去，我也是醉了！ 70 father[i]=i; //不知道咋回事 71 k=0; 72 getchar(); 73 74 for(int i=1;i<t;i++) 75 { 76 scanf("%c %d",&a,&n); 77 for(int j=0;j<n;j++,k++) 78 { 79 scanf(" %c %d",&c,&m); 80 p[k].u=a-'A'+1; 81 p[k].v=c-'A'+1; 82 p[k].w=m; 83 } 84 getchar(); 85 } 86 qsort(p,k,sizeof(struct stu),cmp); 87 //for(int i=0;i<k;i++) 88 //printf("%d %d %d ",p[i].u,p[i].v,p[i].w); 89 printf("%d ",kruskal()); 90 } 91 return 0; 92 }