POJ 2421 Constructing Roads

想法：
    與POJ 1751是一樣的，先依題目將已連結的點連起來，剩下的再用Kruskal做最小生成樹，並累積最小生成樹的邊長和。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	struct Edge{
	int A;
	int B;
	int Len;
	}E[15001];
	int Set[2001];
	bool cmp(const Edge &A, const Edge &B);
	void Set_Initial(const int &N);
	int Find_Root(const int &x);
	bool Union(const Edge &E);
	void Union(int x, int y);
	int main()
	{
	int N, M, A, B, L;
	while (scanf("%d", &N) == 1) {
	int nOfE = 0;
	for (int i = 1; i <= N; ++i) {
	for (int j = 1; j <= N; ++j) {
	scanf("%d", &A);
	if (!A) continue;
	E[nOfE].A = i;
	E[nOfE].B = j;
	E[nOfE++].Len = A;
	}
	}
	sort(E, E + nOfE, cmp);
	Set_Initial(N);
	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
	scanf("%d %d", &A, &B);
	Union(A, B);
	}
	int sum = 0;
	for (int i = 0, currentEdge = 0; i < nOfE; ++i)
	if (Union(E[i])){
	++currentEdge;
	sum += E[i].Len;
	}
	printf("%d\n", sum);
	}
	}
	bool cmp(const Edge &A, const Edge &B) {
	return A.Len < B.Len;
	}
	void Set_Initial(const int &N)
	{
	for (int i = 1; i <= N; ++i)
	Set[i] = i;
	}
	int Find_Root(const int &x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = Find_Root(Set[x]);
	}
	void Union(int x, int y)
	{
	x = Find_Root(x);
	y = Find_Root(y);
	if (x != y)
	Set[x] = y;
	}
	bool Union(const Edge &E)
	{
	int x = Find_Root(E.A);
	int y = Find_Root(E.B);
	if (x != y) {
	Set[x] = y;
	return true;
	}
	return false;
	}

view raw [POJ] 2421 Constructing Roads.cpp hosted with ❤ by GitHub