[백준] 친구비(16562)

문제 링크 : [백준] 친구비(16562)

문제 설명

주어진 모든 사람과 친구가 되려고 하는데 필요한 비용을 구하세요.
단, 친구의 친구는 친구라는 조건을 가지고 최소한의 비용만으로 모든 사람과 친구가 되어야합니다.

입력

N(친구의 수, 1 <= N <= 10,000)
M(친구 관계의 수, 1 <= M <= 10,000)
K(사용할 수 있는 최대 비용, 1 <= 10,000,000)
V_i(i번째 친구와 친구가 되기 위한 비용, 1 <= V_i <= 10,000)
A_i B_i(친구 관계)

5 3 20
10 10 20 20 30
1 3
2 4
5 4

출력

20

카테고리

#DisjointSet

시간 복잡도 상한

O(MlogN) 혹은 O(NlongM)

해결 방법

1. 친구의 친구는 친구이기 때문에, 친구 관계를 이용하여 친구로 이어질 수 있는 모든 사람들을 그룹으로 묶습니다.
2. 그룹으로 묶인 사람들 중 한명만 친구를 맺으면 그 그룹의 모든 사람과 친구가 될 수 있습니다.
3. 즉, 각 그룹별로 최소의 비용만 갖는 사람과 친구를 맺으면 됩니다.
4. 그룹을 맺는 방법은 Disjoint set을 사용하면 O(N)에 모든 사람을 그룹으로 묶을 수 있습니다.
5. for문을 이용하여 그룹별 최소 비용을 찾고, 그 값들을 출력합니다.
6. 단, 총 비용이 K보다 크다면 Oh no를 출력해야 합니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,k,d[10001],e[10001],s[10001],i,a,b;
int f(int a){
    return e[a]==a?a:e[a]=f(e[a]);
}
void u(int a,int b){
    e[f(a)]=f(b);
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++)scanf("%d",d+i),e[i]=i;
    while(m--){
        scanf("%d%d",&a,&b);
        u(a,b);
    }
    for(i=1;i<=n;i++)s[f(i)]=s[f(i)]?min(s[f(i)],d[i]):d[i];
    for(a=0,i=1;i<=n;i++)a+=s[i];
    if(k<a)printf("Oh no");
    else printf("%d",a);
}