xfstart07
Get busy living or get busy dying
并查集+Kruskal

  1 /*
  2  * Problem: 最小生成树
  3  * Author: Xu Fei
  4  * Time: 2010.8.3 14:58
  5  * Method: Kruskal
  6  */
  7 #include<iostream>
  8 #include<cstdio>
  9 using namespace std;
 10 
 11 const int MaxN=100,MaxM=10000;
 12 
 13 struct edge
 14 {
 15     int x,y,c;
 16 }E[MaxM];
 17 int N,M;
 18 int Ans;
 19 int P[MaxN];
 20 int H[MaxN];
 21 
 22 void init()
 23 {
 24     int i;
 25     scanf("%d%d",&N,&M);
 26     for(i=1;i<=M;++i)
 27     {
 28         scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].c);
 29     }
 30 }
 31 inline void swap(edge &a,edge &b)
 32 {
 33     edge tmp;
 34     tmp=a;
 35     a=b;
 36     b=tmp;
 37 }
 38 void qsort(int s,int t)
 39 {
 40     int i=s,j=t,mid;
 41     mid=E[(i+j)>>1].c;
 42     while(i<=j)
 43     {
 44         while(E[i].c < mid)
 45             i++;
 46         while(E[j].c > mid)
 47             j--;
 48         if(i<=j)
 49         {
 50             swap(E[i],E[j]);
 51             i++
 52             j--;
 53         }
 54     }
 55     if(s<j)
 56         qsort(s,j);
 57     if(i<t)
 58         qsort(i,t);
 59 }
 60 inline int Find(int x)
 61 {
 62     if(x != P[x])
 63         P[x]=Find(P[x]);
 64     return P[x];
 65 }
 66 void change(int x,int y)
 67 {
 68     if(H[x] > H[y])
 69         P[y]=x;
 70     else if(H[y] > H[x])
 71         P[x]=y;
 72     else
 73     {
 74         H[x]++;
 75         P[y]=x;
 76     }
 77 }
 78 void solve()
 79 {
 80     int i,k,x,y;
 81     qsort(1,M);
 82     for(i=1;i<=N;++i)
 83         P[i]=i,H[i]=1;
 84     Ans=k=0;
 85     for(i=1;i<=M;++i)
 86     {
 87         x=Find(E[i].x);
 88         y=Find(E[i].y);
 89         if(x != y)
 90         {
 91             Ans+=E[i].c;
 92             k++;
 93             if(k == N-1)
 94                 break;
 95             change(x,y);
 96         }
 97     }
 98     printf("%d\n",Ans);
 99 }
100 int main()
101 {
102     init();
103     solve();
104     return 0;
105 }

posted on 2010-08-03 14:59 xfstart07 阅读(119) 评论(0)  编辑 收藏 引用 所属分类: 算法学习图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理