Time Limit: 1000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s):
14103 Accepted Submission(s): 5824
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的
N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
Output
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
Sample Input
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
Sample Output
3 ?
Source
题解：显然就是求解最小生成树，用prim算法实现。
1: #include<stdlib.h> 2: #include<stdio.h>3: #include<string.h>
4: #define INF 10000001
5: #define maxn 101
6: int map[maxn][maxn];
7: int cost[maxn];
8: int chosed[maxn]; //
9: int count; //统计点的个数
10: long total_cost; //总费用
11: void init_map(int n){ //初始化二阶矩阵
12: int i,j;
13: for(i=1;i<=n;i++)
14: for(j=1;j<=n;j++)
15: map[i][j]=(i==j?0:INF); 16: }17: void init(int n){
18: int i;
19: memset( chosed , 0 , sizeof(chosed));
20: chosed[1]=1; 21: count=1;22: for( i = 1 ; i <= n ; i++ )
23: cost[i] = map[1][i]; 24: } 25: 26: void prim(int n){
27: int min,min_idx;
28: int i;
29: total_cost=0;30: while( count <=n ){
31: min = INF; 32: for( i = 2 ; i <= n ; i++ ){
33: if( !chosed[i] && cost[i] < min){ //选择尚未choosed的node中的最小的权重的边
34: min_idx=i; 35: min=cost[i]; 36: } 37: }38: if( min == INF )
39: return;
40: chosed[min_idx]=1; 41: total_cost+=min; 42: count++; 43: for( i = 1 ; i <= n ; i++) //按照这个node更新cost[]
44: if(!chosed[i]&& map[min_idx][i]<cost[i])
45: cost[i] = map[min_idx][i]; 46: } 47: } 48: 49: int main(){
50: int road,node,i;
51: while(scanf("%d %d",&road,&node)!=EOF&& road ){
52: init_map(node); 53: count=0;54: while(road--){
55: int a,b,c;
56: scanf("%d %d %d",&a,&b,&c);
57: map[a][b]=c; 58: map[b][a]=c; 59: } 60: init(node); 61: prim(node);62: if(count==node)
63: printf("%ld\n",total_cost);
64: else
65: printf("?\n");
66: } 67: }hdu 1863 - 畅通工程,布布扣,bubuko.com
原文：http://www.cnblogs.com/ZJUT-jiangnan/p/3588715.html