首页 > ACM题库 > 九度OJ > 九度-1017-还是畅通工程[解题代码]
2013
12-12

九度-1017-还是畅通工程[解题代码]

题目来源:2006年浙江大学计算机及软件工程研究生机试真题

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

    测试输入包含若干测试用例。每个测试用例的第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

cpp 代码如下:
#include <iostream>
using namespace std;
bool visited[101];
int ans;
int map[101][101];
int MAX = 10000000;
int m,a,b,c;
void solve(){
	ans = 0;
		visited[0] = true;
		for(int i=1; i<m; i++){
			int index = 0;
			long min = MAX;
			for(int j=1; j<m; j++){
				if(!visited[j] && map[0][j] < min){
					min = map[0][j];
					index = j;
				}
			}
			ans += map[0][index];
			map[0][index] = 0;
			visited[index] = true;
			long temp = 0;
			for(int j=0; j<m; j++){
				if(!visited[j] && map[index][j] < MAX){
					temp = map[0][index] + map[index][j];
					if(temp < map[0][j])
						map[0][j] = temp;
				}
			}
		}

}
int main() {
	while(cin >> m,m){
		for(int i=0; i<m; i++){
			visited[i] = false;
			for(int j=0; j<m; j++)
				map[i][j] = MAX;
		}
		int n = m*(m-1)/2;
		for(int i=0; i<n; i++){
			cin >> a >> b >> c;
			a--;
			b--;
			if(map[a][b] > c)
			{
				map[a][b] = c;
				map[b][a] = c;
			}
		}
		 solve();
			cout << ans << endl;

	}
	return 0;
}

/**************************************************************
	Problem: 1017
	User: coder
	Language: C++
	Result: Accepted
	Time:20 ms
	Memory:1560 kb
****************************************************************/


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts