还是畅通工程
Crawling in process...
Crawling failed
Time Limit:2000MS
Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最小的公路总长度。
Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
Sample Output
3 5
Hint
Hint
Huge input, scanf is recommended.
#include <stdio.h> #include <string.h> #define maxnum 108 #define maxint 999999 int n,m; int c[maxnum][maxnum]; void prem() { int s[maxnum]; int dis[maxnum]; int ans = 0; memset(s,0,sizeof(s)); int i,j; for(i = 1; i<=m; i++) dis[i] = c[1][i]; s[1] = 1; for(i = 1; i<m; i++) { int pos,min; min = maxint; for(j = 1; j<=m; j++) { if(!s[j] && min > dis[j]) { pos = j; min = dis[j]; } } if(maxint == min) break; s[pos] = 1; ans += min; for(j = 1; j<=m; j++) { if(!s[j] && dis[j] > c[pos][j]) dis[j] = c[pos][j]; } } int oo = 1; for(i=1; i<=m; i++) { if(s[i] == 0) { oo = 0; break; } } if(oo == 0) printf("?\n"); else printf("%d\n",ans); } int main() { while(~scanf("%d",&m),m) { int i,j,p,e,len,n; n = m*(m-1)/2; for(i = 1; i<=m; i++) { for(j = 1; j<=m; j++) { c[i][j] = maxint; } } for(i = 1; i<=n; i++) { scanf("%d%d%d",&p,&e,&len); if(len < c[p][e]) { c[p][e] = len; c[e][p] = len; } } prem(); } return 0; }