继续畅通工程 （C++代码）

解题思路:

        还是最小生成树，只需要把已经修建好的路权值改为 0 即可 。

参考代码:

#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] && index != i)
				dis[i] = Map[index][i];
	}
	return total;
}


int main() {
	int paths, pos1, pos2, weigth, finish;
	while (~scanf("%d", &point) && point) {
		init(); paths = point*(point - 1) / 2;
		while (paths--) {
			scanf("%d%d%d%d", &pos1, &pos2, &weigth, &finish);
			if (finish == 0) {
				Map[pos1][pos2] = weigth; Map[pos2][pos1] = weigth;
			}
			else {
				Map[pos1][pos2] = 0; Map[pos2][pos1] = 0;
			}
		}
		cout << prim() << endl;
	}
}