UVa 10369 Arctic Network

題意：
    有S個衛星，以及P個城市，如果兩個城市都有衛星的話，那麼不管距離多遠都能通訊，否則就只能靠radio通訊，而靠radio通訊的最遠的兩個城市距離為D，現在求如果每個城市都要通訊的話，那麼D最小為多少?
以Sample Input舉例：
(0,300)~(0,600)=300之間，各使用一個satellite，透過satellite來溝通，(0,100)~(0,300)=200和(0,600)~(150,750)=212.13則使用radio，因此D至少要212.13

想法：
    P個城市代表有(P-1)條邊，而用Kruskal演算法做出最小生成樹，做Kruskal的過程中將邊長記錄下來，共有(P-1)條，然後把其中最長的(S-1)條邊分配給衛星，剩下的邊的最大値就是D。

	#include <cstdio>
	#include <cmath>
	#include <algorithm>
	using namespace std;
	struct Point{
	int X;
	int Y;
	}point[501];
	struct Edge {
	int a_index;
	int b_index;
	double Len;
	}E[501 * 501];
	int nOfE;
	int Set[501];
	bool cmp(const Edge &A, const Edge &B) {
	return A.Len < B.Len;
	}
	int Find_Root(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = Find_Root(Set[x]);
	}
	bool Union(const Edge &E, vector<double> &LenOfEdge)
	{
	int a = Find_Root(E.a_index);
	int b = Find_Root(E.b_index);
	if (a != b) {
	Set[a] = b;
	LenOfEdge.push_back(E.Len);
	return true;
	}
	return false;
	}
	int main()
	{
	int Case;
	int S, P;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &S, &P);
	for (int i = 0; i < P; ++i) {
	scanf("%d %d", &point[i].X, &point[i].Y);
	Set[i] = i;
	}
	nOfE = 0;
	for (int i = 0; i < P; ++i) {
	for (int j = i + 1; j < P; ++j) {
	double L = sqrt(pow(point[i].X - point[j].X, 2) + pow(point[i].Y - point[j].Y, 2));
	E[nOfE++] = {i, j, L};
	}
	}
	sort(E, E + nOfE, cmp);
	vector<double> LenOfEdge;
	for (int i = 0, nOfEdges = 0; nOfEdges != P - 1; ++i) {
	if (Union(E[i], LenOfEdge)) ++nOfEdges;
	}
	printf("%.2f\n", LenOfEdge[P-S-1]);
	}
	}

view raw [UVa] 10369 Arctic Network.cpp hosted with ❤ by GitHub