Constructing Roads

3
0 990 692
990 0 179
692 179 0
1
1 2

179

思路就是构造一棵最小生成树，所以将距离排序，从小到大依次并入，直到集合数为1为止。

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXX = 102;

typedef struct Road{
	int x, y, dist;
	Road(int ix, int iy, int idist){
		x = ix;
		y = iy;
		dist = idist;
	}
}road;

int n,roads,length;
vector<road> vec;

int pre[MAXX];
bool yes[MAXX][MAXX] = { 0 };

void init(int n){
	for (int i = 1; i <= n; ++i){
		pre[i] = i;
	}
}

int root(int x){
	if (x != pre[x]){
		pre[x] = root(pre[x]);
	}
	return pre[x];
}

bool merge(int x, int y){
	int fy = root(y);
	int fx = root(x);

	bool mark = false;

	if (fx != fy){
		pre[fx] = fy;
		mark = true;
		--roads;
	}

	return mark;
}

bool cmp(road a, road b){
	return a.dist < b.dist;
}

int main(){

	//freopen("in.txt", "r", stdin);
	int dist, t, x, y;

	while (scanf("%d", &n) != EOF){
		roads = n - 1;
		vec.clear();
		memset(yes, 0, sizeof(yes));

		for (int i = 1; i <= n; ++i){
			for (int j = 1; j <= n; ++j){
				scanf("%d", &dist);
				if (i == j || i > j)continue;//重复的路径不进行添加
				vec.push_back(road(i, j, dist));
			}
		}

		sort(vec.begin(), vec.end(), cmp);

		init(n);

		scanf("%d", &t);

		while (t--){
			scanf("%d %d", &x, &y);
			merge(x, y);
			yes[x][y] = true;
		}

		length = 0;
		vector<road>::iterator ite = vec.begin();
		for (; ite != vec.end() && roads != 0; ++ite){
			x = (*ite).x;
			y = (*ite).y;
			dist = (*ite).dist;
			if (yes[x][y])continue;
			if (merge(x, y))length += dist;
		}

		printf("%d\n", length);
	}
	return 0;
}

HDU 1102 Constructing Roads （裸的并查集）,布布扣,bubuko.com

HDU 1102 Constructing Roads （裸的并查集）

原文：http://blog.csdn.net/iaccepted/article/details/29220347