Bibidi

16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 제목부터 슬픈 문제. 서로 연결되어 있는 것들을 처리해야 해서 처음엔 Connected Component를 구해서 어찌어찌 처리해야 하나 했지만 친구비를 아끼기 위해 친구 집합의 최소 친구비를 구해야 된다. 트리를 이용하면 루트에 최소 친구비를 업데이트 할 수 있고 두 트리를 합칠 땐 유니온 파인드를 이용하면 된다. 유니온 파인드의 merge를 구현할 때 왼쪽을 우리와 이미 친구인 집합 오른쪽을 새로 친구가 되는 집합..