还是畅通工程 （C++代码）

解题思路:

        最小生成树。

        输入数据量大的话用 cin 就显得很慢，scanf 就快很多了，或者手动解除同步。

        
参考代码:

#include <bits/stdc++.h>
#define Inf 0x3F3F3F3F
using namespace std;

int  Map[102][102];
int  dis[102];
bool vis[102];
int point;

void init() {
	memset(Map,  0x3F, sizeof(Map));
	memset(vis, false, sizeof(vis));
	for (int i = 1; i <= point; i++)
		Map[i][i] = 0;
}

int prim() {
	for (int i = 1; i <= point; i++)
		dis[i] = Map[1][i];
	vis[1] = true;
	
	int total = 0;
	for (int i = 1; i < point; i++) {
		int Min = Inf, index;

		for (int pos = 1; pos <= point; pos++)
			if (!vis[pos] && Min > dis[pos]) {
				Min = dis[pos]; index = pos;
			}
		total += dis[index]; vis[index] = true;

		for (int i = 1; i <= point; i++)
			if (dis[i] > Map[index][i] && Map[index][i] != 0)
				dis[i] = Map[index][i];
	}
	return total;
}

int main() {
	int paths, pos1, pos2, weig;
	while (~scanf("%d", &point) && point) {
		init(); paths = point*(point - 1) / 2;

		while (paths--) {
			scanf("%d%d%d", &pos1, &pos2, &weig);
			Map[pos1][pos2] = weig;
			Map[pos2][pos1] = weig;
		}
		cout << prim() << endl;
	}
}