1017

// 1017_还是畅通工程.cpp : 定义控制台应用程序的入口点。 //题目1017：还是畅通工程 //时间限制：1 秒内存限制：32 兆特殊判题：否提交：6085解决：3025 //题目描述： //某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 //输入： //测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 //当N为0时，输入结束，该用例不被处理。 //输出： //对每个测试用例，在1行里输出最小的公路总长度。 //样例输入： //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 //样例输出： //3 //5 //来源： //2006年浙江大学计算机及软件工程研究生机试真题 #include "stdafx.h" #include "stdio.h" #include "iostream" #include "limits.h" #include "string.h" using namespace std; #define MAX 110 int N; int dist[MAX][MAX],lowcost[MAX],visit[MAX]; int main() { while(cin>>N && N){ int x,y,z; for(int i = 0;i<N*(N-1)/2;i++){ cin>>x>>y>>z; dist[x][y] = dist[y][x] = z; } memset(visit,0,sizeof(visit)); for(int i = 2;i<=N;i++) lowcost[i] = INT_MAX; int start = 1; //每次加入集合的点（第一个点是1） int min_dist = 0; //累加的距离 int count = 1; //已经加入集合的点的个数 int cursor = start; //记录当前距集合最小距离的位置 visit[start] = 1; while(count<N){ for(int i =1;i<=N;i++){ if(!visit[i]){ lowcost[i] = min(lowcost[i],dist[start][i]); cursor = lowcost[i]<lowcost[cursor]?i:cursor; } } start = cursor; visit[start] = 1; count++; min_dist += lowcost[start]; lowcost[cursor] = INT_MAX; } cout<<min_dist<<endl; } return 0; } /* 1.INT_MAX */