1524 - 畅通工程2
时间限制 : 1 秒
内存限制 : 32 MB
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
题目输入
测试输入包含若干测试用例。每个测试用例的第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; }
Java解答
import java.util.Scanner; /** * * @author gzf19902016 */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); // 道路数 int m = scanner.nextInt(); // 村庄数 if (n == 0) { break; } int[] village = new int[m + 1], villageLength = new int[m + 1]; int villageNum = 0, from, to, length; distance[] graph = new distance[n]; for (int i = 0; i < n; i++) { graph[i] = new distance(); from = scanner.nextInt(); to = scanner.nextInt(); length = scanner.nextInt(); if (i == 0) { graph[i].from = from; graph[i].to = to; graph[i].length = length; } else { int j; for (j = i - 1; j >= 0 && graph[j].length > length; j--) { graph[j + 1].from = graph[j].from; graph[j + 1].to = graph[j].to; graph[j + 1].length = graph[j].length; } graph[j + 1].from = from; graph[j + 1].to = to; graph[j + 1].length = length; } } for (int i = 0; i < n; i++) { from = graph[i].from; to = graph[i].to; if (village[from] == 0 && village[to] == 0) { //都不在,散点 village[from] = village[to] = ++villageNum; villageLength[villageNum] = graph[i].length; } else if (village[from] == 0 && village[to] != 0) { //孤点在外的情况 village[from] = village[to]; villageLength[village[to]] += graph[i].length; } else if (village[from] != 0 && village[to] == 0) { village[to] = village[from]; villageLength[village[from]] += graph[i].length; } else { if (village[from] != village[to]) { //合并组, 规则: 编号小的组合并编号大的组 int little = village[from] < village[to] ? village[from] : village[to]; int high = village[from] > village[to] ? village[from] : village[to]; for (int j = 1; j <= n; j++) if (village[j] == high) village[j] = little; villageLength[little] += (villageLength[high] + graph[i].length); villageLength[high] = 0; } } if (isAllIn(village)) break; } if (isAllIn(village)) System.out.println(villageLength[1]); else System.out.println("?"); } } private static boolean isAllIn(int[] village) { for(int i = 1; i < village.length; i++){ if(village[i] != village[1]) return false; } return true; } private static class distance { public int from; public int to; public int length; } }