어흥
[백준 10021] Watering the Fields (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/10021
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;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 10836] 여왕벌 (JAVA) (0) | 2020.07.26 |
---|---|
[백준 17182] 우주 탐사선 (C++) (0) | 2020.07.08 |
[백준 15591] MooTube (Silver) (C++) (0) | 2020.06.23 |
[백준 17780] 새로운 게임 (C++) (0) | 2020.06.18 |
[백준 15681] 트리와 쿼리 (C++) (0) | 2020.06.15 |
Comments