[백준 10021] Watering the Fields (C++)

문제 링크: https://www.acmicpc.net/problem/10021

10021번: Watering the Fields

1. 주의할 점

- MST문제로, MST 생성할 수 없다면 -1을 출력한다

 

2. 구현

- 크루스칼 알고리즘을 통해 MST를 해결한다

- 모든 Node에 대한 정보를 X[], Y[]에 담는다

- 모든 Node를 서로 다른 Node와 비교한 유클리드 계산값을 시작점과 끝점과 함께 우선순위큐에 넣는다

- 우선순위큐에서 1개씩 꺼내면서 유클리드값이 Maxi보다 작다면 Continue하고 그렇지 않은 경우, 서로 같은 부모를 뒀는지 확인한다. 서로 같은 부모인 경우 이미 연결됐으므로 무시하고, 같은 부모가 아닌 경우 해당 간선을 연결한다

- MST가 완성되지 않은 경우(MST : Node가 N개면 N-1개의 간선을 사용) Result값을 -1로 한다

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	int from, to;
	long long val;
};
struct cmp {
	bool operator()(info& a, info& b) {
		return a.val > b.val;
	}
};
info tmp;
int x[2001], y[2001], par[2001];

int find_par(int p) {
	if (par[p] == p) return p;
	return par[p] = find_par(par[p]);
}

void make_union(int a, int b) {
	a = find_par(a);
	b = find_par(b);
	if (a > b) par[a] = b;
	else if (a < b) par[b] = a;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, maxi, conn = 0;
	long long result = 0;
	cin >> node >> maxi;
	for (int i = 1; i <= node; i++) {
		cin >> x[i] >> y[i];
		par[i] = i;
	}
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 1; i < node; i++) {
		for (int j = i + 1; j <= node; j++) {
			long long dx = x[i] - x[j];
			long long dy = y[i] - y[j];
			long long v = dx * dx + dy * dy;
			tmp.from = i;
			tmp.to = j;
			tmp.val = v;
			pq.push(tmp);
		}
	}
	while (!pq.empty()) {
		int cf = pq.top().from;
		int ct = pq.top().to;
		long long cv = pq.top().val;
		pq.pop();
		if (cv < maxi) continue;
		int pf = find_par(cf);
		int pt = find_par(ct);
		if (pf == pt) continue;
		make_union(cf, ct);
		result += cv;
		conn++;
		if (conn == node - 1) break;
	}
	if (conn != node - 1) result = -1;
	cout << result;
	return 0;
}