[백준] 16562 친구비

문제 출처: www.acmicpc.net/problem/16562

16562번: 친구비

: 친구들을 사귀는데 비용이 주어지고, 최소의 돈을 들이면서 모든 친구들과 친해지기 위한 비용을 찾는다.

: 만약 제한된 금액 안에서 모든 친구들과 친해질 수 없다면 "Oh no"를 출력할 수 있도록 한다.

: union-find 알고리즘을 통해 각각의 관계마다 처리해 준다.

: 그 후 find를 통해 가장 위에 있는 대표자로 바꿀 수 있도록 하고

: 같은 대표자를 가지는 친구들마다 금액을 비교해서 최소 금액을 찾도록 한다.

: 처음에 주어졌던 제한 금액보다 크면 모든 친구와 사귈 수 없으므로 Oh no를 출력하고

: 그게 아니라면 친해지기 위한 최소 금액을 출력한다.

 

--------------------------------------------------------------------------------------------------------------------------------

: 다른 풀이를 보니 최소 금액을 찾는 과정에서 처음에 union할 때 금액을 비교해서 작은거에 붙여줄 수 있도록 하고

: 나중에 i와 p[i]가 같은 경우만 다 더해줄 수도 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M, K;
	static int[] p;
	static int[] price;
	static void make() {
		for(int i = 1; i < N+1; i++) {
			p[i] = i;
		}
	}
	static int find(int i) {
		if(p[i] == i) return i;
		return p[i] = find(p[i]);
	}
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot) return false;
		p[bRoot] = aRoot;
		return true;
	}
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		p = new int[N+1];
		price = new int[N+1];
		make();
		st = new StringTokenizer(br.readLine());
		
		for(int i = 1; i < N+1; i++) {
			price[i] = Integer.parseInt(st.nextToken());
		}
		int cnt = N;
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(union(a, b)) cnt--;
		}
		boolean[] arr = new boolean[N+1];
		
		for(int i = 1; i < N+1; i++) {
			arr[find(i)] = true;
		}
		
		for(int i = 1; i < N+1; i++) {
			if(price[i] < price[p[i]]) price[p[i]] = price[i];
		}
		int ans = 0;
		for(int i = 1; i < N+1; i++) {
			if(arr[i]) ans+=price[i];
		}
		if(K >= ans) System.out.println(ans);
		else System.out.println("Oh no");

	}
}