친구끼리 Union해주는데 이 때 친구비가 제일 저렴한 애가 루트가 되도록 합친다.
#include <bits/stdc++.h>
using namespace std;
int N, M, K, cost[10000];
typedef struct _DisjSet {
int parent[1000001] = {0,};
void init(int n) {
for (int i = 0; i < n+1; i++) {
parent[i] = i;
}
}
int find(int n) {
if (parent[n] == n) return n;
return parent[n] = find(parent[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
if (cost[n1] < cost[n2]) parent[n2] = n1;
else parent[n1] = n2;
}
} DisjSet;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
DisjSet d;
d.init(N);
for (int i = 0; i < N; i++) {
cin >> cost[i];
}
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
d.Union(a-1, b-1);
}
int ans = 0;
for (int i = 0; i < N; i++) {
if (d.find(N) == d.find(i)) continue;
ans += cost[d.find(i)];
d.Union(N, i);
}
if (ans <= K) cout << ans;
else cout << "Oh no";
return 0;
}
맨 처음에는 cost[루트 인덱스]에 각 집합의 최소 친구비가 들어가도록 짰는데 잘 안됐다. 왜안됐지? 솔직히 아직도 잘 모르겠다.
for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; d.Union(a-1, b-1); cost[d.find(a-1)] = min(cost[d.find(a-1)], min(cost[a-1], cost[b-1])); }
이렇게 했는데 어딘가 빼먹는게 있었나봄.. 유니온 파인드에서는 최대한 루트만 참조하도록 짜야겠다.
친구비 얼마인가요 계좌 불러주시죠