백준 16562 친구비 혼내주기

 

유니온 파인드를 이용해 한명의 친구로 퉁칠수 있는 각 집합의 최소 친구비를 구한뒤, 가진 돈과 비교해서 결과를 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int cost[10000], parent[10000], minCost[10000];

int find(int u){
    if(parent[u] < 0) return u;
    return parent[u] = find(parent[u]);
}

void merge(int u, int v){
    u = find(u); v = find(v);
    if(u == v) return ;

    if(u > v) swap(u, v);
    parent[u] += parent[v];
    parent[v] = u;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, k; cin >> n >> m >> k;
    for(int i = 0; i < n; ++i) cin >> cost[i];
    memset(parent, -1, sizeof(parent));
    memset(minCost, 0x3f, sizeof(minCost));
    
    int a, b;
    for(int i = 0; i < m; ++i){
        cin >> a >> b; --a; --b; 
        merge(a, b);
    }
    
    vector<bool> list(n, false);
    for(int i = 0; i < n; ++i){
        int f = find(i);
        list[f] = true;
        minCost[f] = min(minCost[f], cost[i]);
    }
    
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(!list[i]) continue;
        ans += minCost[i];
    }

    if(ans <= k) cout << ans;
    else cout << "Oh no";
}