POJ 1751 Highways

題意：
    依序給你N個城市的座標，然後接下M行說明哪些城市已經相連，題目要求盡可能用最短的距離把所有的城市連起來。
想法：
    先把兩兩城市的距離算出來，共有C(N,2)條邊長，將這些邊由小大到排序，然後做Kruskal演算法，將所有城市連起來。
    原本49~53行原本我是打算如果總共已經做了(N-1)條邊就跳出for loop，但是WA，後來想想應該是測資給的已經存在的邊會形成一個環(cycle)，所以就不可能為最小生成樹，邊長總數會大於(N-1)條。

	#include <cstdio>
	#include <cmath>
	#include <algorithm>
	using namespace std;
	struct Point{
	int x;
	int y;
	}P[751];
	struct Edge{
	int A;
	int B;
	double Len;
	}E[751*751];
	int Set[751];
	void Set_Initial(const int &N);
	int Find_Root(const int &x);
	void Union(int x, int y);
	bool Union(const Edge &E);
	bool cmp(const Edge &A, const Edge &B) {
	return A.Len < B.Len;
	}
	int main()
	{
	int N, M;
	while (scanf("%d", &N) == 1) {
	for (int i = 1; i <= N; ++i)
	scanf("%d %d", &P[i].x, &P[i].y);
	int nOfE = 0;
	for (int i = 1; i <= N; ++i)
	for (int j = i + 1; j <= N; ++j) {
	E[nOfE].A = i;
	E[nOfE].B = j;
	E[nOfE++].Len = sqrt(pow(P[i].x-P[j].x, 2) + pow(P[i].y - P[j].y, 2));
	}
	sort(E, E + nOfE, cmp);
	Set_Initial(N);
	int A, B;
	scanf("%d", &M);
	for (int i = 0; i < M; ++i) {
	scanf("%d %d", &A, &B);
	Union(A, B);
	}
	for (int i = 0; i < nOfE; ++i) {
	if (Union(E[i])) {
	printf("%d %d\n", E[i].A, E[i].B);
	}
	}
	}
	}
	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] 1751 Highways.cpp hosted with ❤ by GitHub