題目鏈接

最小生成樹的題。克魯斯卡爾算法。

View Code 1 #include <stdio.h> 2 #define N 100 3 #define M 5000 4 struct node 5 { 6 int a,b,d; 7 }edge[M]; 8 int n; 9 int p[N]; 10 void make_set() 11 { 12 int i; 13 for(i=1;i<=n;i++) p[i]=i; 14 } 15 int find_set(int i) 16 { 17 return i==p[i]?p[i]:(p[i]=find_set(p[i])); 18 } 19 void union_set(int i,int j) 20 { 21 i=find_set(i),j=find_set(j); 22 p[j]=i; 23 } 24 int cmp(const void *a,const void *b) 25 { 26 return ((struct node*)a)->d-((struct node*)b)->d; 27 } 28 int main() 29 { 30 int i,ans,cnt,x,y,z,f; 31 while(scanf("%d",&n)&&n) 32 { 33 make_set(); 34 cnt=0; 35 for(i=0;i<n*(n-1)/2;i++) 36 { 37 scanf("%d%d%d%d",&x,&y,&z,&f); 38 edge[i].a=x,edge[i].b=y,edge[i].d=z; 39 if(f) union_set(x,y),cnt++; 40 } 41 ans=0; 42 qsort(edge,n*(n-1)/2,sizeof(edge[0]),cmp); 43 for(i=0;cnt<n-1&&i<n*(n-1)/2;i++) 44 { 45 if(find_set(edge[i].a)==find_set(edge[i].b)) continue; 46 ans+=edge[i].d; 47 union_set(edge[i].a,edge[i].b); 48 cnt++; 49 } 50 printf("%d\n",ans); 51 } 52 return 0; 53 }

?

轉載于:https://www.cnblogs.com/algorithms/archive/2012/04/20/2459863.html

總結

以上是生活随笔為你收集整理的HDOJ1879(继续畅通工程)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。