[백준 4343] Arctic Network

https://www.acmicpc.net/problem/4343

4343번: Arctic Network

 

요구사항

전초 기지를 모두 이을 때 최소가 되는 D 구하기

 

풀이

최소가 되는 D를 구하기 위해서 제일 작은거를 위성 수 만큼 연결 해줄때 제일 마지막으로 연결된 것이 정답이다.

Union-Find와 힙을 이용하여 정답 구하기

 

#include <iostream>
#include <queue>
#include <math.h>
#include <algorithm>
#include <functional>
using namespace std;
typedef pair<double, pair<int, int> > q;
typedef long long ll;
struct go {
	int x;
	int y;
};
int n, m;
go map[550];
int parent[550];
int Find(int a) {
	if (parent[a] == a) return a;
	else return parent[a] = Find(parent[a]);
}
bool Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a == b) return false;
	if (a != b) {
		parent[a] = b;
		return true;
	}

}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		priority_queue<q> pq;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) {
			int x, y;
			parent[i] = i;
			scanf("%d%d", &x, &y);
			map[i].x = x;
			map[i].y = y;
		}
		for (int i = 1; i <= m; i++) {
			for (int j = i + 1; j <= m; j++) {
				int xdist = abs((map[i].x - map[j].x)) * abs((map[i].x - map[j].x));
				int ydist = abs((map[i].y - map[j].y)) * abs((map[i].y - map[j].y));
				double dist = sqrt(xdist + ydist);
				pq.push(make_pair(-dist,make_pair(i,j)) ) ;
			}
		}
		double ans;
		int first_value;
		int second_value;
		while (true) {
			//cout << "A "<<n << endl;
			ans = -pq.top().first;
			first_value = pq.top().second.first;
			second_value = pq.top().second.second;
			pq.pop();
			//cout << ans << endl;
			if (Union(first_value, second_value)) {

				n--;
			}
			if (n == 0)
				break;
		}
		printf("%.2f\n", ans);
	}
}