1524 - 畅通工程2
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
题目输入
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
题目输出
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
输入/输出样例
题目输入
3 4 1 2 1 2 3 2 3 4 3 2 4 1 2 1 3 4 2 0 5
题目输出
6 ?
C语言解答
#include <stdio.h> typedef struct Road { int a,b; int w; }Road; int n,m; Road road[101]; int set[101]; int root(int a) { while(a!=set[a]) a=set[a]; return a; } void sort(void) { int i,j; Road t; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(road[i].w>=road[j].w) { t = road[i]; road[i] = road [j]; road[j] = t; } } } } int main(void) { int i,j; int a,b,w; int s=0; while(scanf("%d%d",&n,&m)==2) { if(n==0)break; for(i=1;i<=m;i++) set[i]=i; for(i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&w); road[i].a = a; road[i].b = b; road[i].w = w; } sort(); s=0; for(i=1;i<=n;i++) { a=road[i].a; b=road[i].b; w=road[i].w; a=root(a); b=root(b); if(a!=b) { set[b]=a; s+=w; } } j=0; for(i=1;i<=m;i++) { if(set[i]==i) j++; } if(j==1) printf("%d\n",s); else printf("?\n"); } return 0; }
C++解答
#include<cstdio> #include<algorithm> using namespace std; struct vi { int start; int end; int cost; }edge[5000],et; int p[101]; int Find(int n) { return n==p[n]?n:p[n]=Find(p[n]); } bool cmp(vi a,vi b) { return a.cost<b.cost; } int main() { int n,m,i,k,sum,flag,ST,EN; while(scanf("%d%d",&n,&m)!=EOF,n) { for(i=1;i<=m;i++) p[i]=i; for(k=i=0;i<n;i++) { scanf("%d%d%d",&et.start,&et.end,&et.cost); edge[k++]=et; } sort(edge,edge+k,cmp); for(sum=i=0;i<k;i++) { ST=Find(edge[i].start); EN=Find(edge[i].end); if(ST!=EN) { p[ST]=EN; sum+=edge[i].cost; } } for(flag=0,i=1;i<=m;i++) if(p[i]==i) flag++; if(flag==1) printf("%d\n",sum); else puts("?"); } return 0; }