繼續(xù)暢通工程

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12717????Accepted Submission(s): 5506

Problem Description 省政府“暢通工程”的目標是使全省任何兩個村莊間都可以實現(xiàn)公路交通（但不一定有直接的公路相連，只要能間接通過公路可達即可）。現(xiàn)得到城鎮(zhèn)道路統(tǒng)計表，表中列出了任意兩城鎮(zhèn)間修建道路的費用，以及該道路是否已經修通的狀態(tài)。現(xiàn)請你編寫程序，計算出全省暢通需要的最低成本。

?

Input 測試輸入包含若干測試用例。每個測試用例的第1行給出村莊數(shù)目N ( 1< N < 100 )；隨后的 N(N-1)/2 行對應村莊間道路的成本及修建狀態(tài)，每行給4個正整數(shù)，分別是兩個村莊的編號（從1編號到N），此兩村莊間道路的成本，以及修建狀態(tài)：1表示已建，0表示未建。

當N為0時輸入結束。

?

Output 每個測試用例的輸出占一行，輸出全省暢通需要的最低成本。

?

Sample Input 3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0

?

Sample Output 3 1 0

?

Author ZJU

?

Source 浙大計算機研究生復試上機考試-2008年

?

Recommend We have carefully selected several similar problems for you:??1301?1213?1198?1878?1877?

?最小生成樹入門題：

1 //531MS 272K 965B G++ 2 #include<stdio.h> 3 #include<string.h> 4 #include<stdlib.h> 5 struct node{ 6 int u,v; 7 int d; 8 }p[10005]; 9 int set[105],n; 10 int cmp(const void*a,const void*b) 11 { 12 return (*(node*)a).d-(*(node*)b).d; 13 } 14 int find(int x) 15 { 16 if(x!=set[x]) set[x]=find(set[x]); 17 return set[x]; 18 } 19 int merge(int a,int b) 20 { 21 int x=find(a); 22 int y=find(b); 23 if(x!=y){ 24 set[x]=y; 25 return 1; 26 } 27 return 0; 28 } 29 int kruskal() 30 { 31 int ans=0; 32 for(int i=0;i<n*(n-1)/2;i++) 33 if(merge(p[i].u,p[i].v)) 34 ans+=p[i].d; 35 return ans; 36 } 37 int main(void) 38 { 39 int st; 40 while(scanf("%d",&n)!=EOF && n) 41 { 42 for(int i=0;i<=n;i++) set[i]=i; 43 for(int i=0;i<n*(n-1)/2;i++){ 44 scanf("%d%d%d%d",&p[i].u,&p[i].v,&p[i].d,&st); 45 if(st==1) merge(p[i].u,p[i].v); 46 } 47 qsort(p,n*(n-1)/2,sizeof(p[0]),cmp); 48 printf("%d\n",kruskal()); 49 } 50 return 0; 51 }

?

?

轉載于:https://www.cnblogs.com/GO-NO-1/p/3710314.html

總結

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

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