学步园

还是畅通工程

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100)；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当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

#include<iostream>
using namespace std;
#define N 1000
#define inf 100000
int c[N][N];
int sum;
void prim(int n,int v){    //结点数，起点
	int lowcost[N] ;  //数组第一个元素(无意义)                                   
	int closest[N] ;   //赋值很大
	bool s[N] ;
	int i,j,k,min;
	for(i=2;i<=n;i++){
		lowcost[i] = c[v][i];  //均与 v (起点)  相连
		closest[i] = v;  //最近相连的点假设是 v
		s[i] = false;  //第 i 个点还未与头点相连
	}
	s[v] = true;  //第一个点加入
	for(i=1;i<n;i++){  //次循环相当于while(n--) 
		min = inf;         //在剩余点遍历                   
		j = v;                 //每次处理一个结点
		for(k=2;k<=n;k++)
			if((lowcost[k]<min)&&(!s[k])){
				min = lowcost[k];
				j = k;
			}
			s[j] = true;  //加入 j 结点
			sum+=min;
			for(k=2;k<=n;k++)
				if((c[j][k]<lowcost[k])&&(!s[k])){
					lowcost[k] = c[j][k];
					closest[k] = j;
				}  //修正离k最近的结点
	    }
}

int main(){
	int n,i,x,y,cost;
	while(cin>>n&&n){
		sum = 0;
		for(i=1;i<=n*(n-1)/2;i++){
			scanf("%d%d%d",&x,&y,&cost);
			c[x][y] = cost;
			c[y][x] = cost;  //*important!
		}
		prim(n,1);
		printf("%d\n",sum);
	}
return 0;
}