백준 16562번: 친구비

문제 : https://www.acmicpc.net/problem/16562

16562번: 친구비

 

 

친구 관계를 유지하기 위해 친구비를 내야하는데, 그 최소의 친구비를 구해야하는 슬픈 문제다. 문제를 읽어보면 바로 알겠지만 집합문제다. 집합문제는 80% 이상 union-find 알고리즘으로 풀리는데 이 문제도 해당된다. 그런데 요즘 set 자료형을 안써서 오랜만에 기억좀 환기할겸 set 자료형을 이용한 풀이로 풀어봤다. 

1번 학생부터 n번 학생까지 모두 처음엔 자기자신만 포함된 set의 포인터를 가지는데, v,w 입력을 받을 때 set을 합쳐주는 과정을 거치는 풀이다. 근데 막상 구현하고 보니 자잘한 오버헤드가 많아 걍 union-find로 푸는게 시간은 훨씬 덜 걸릴거 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <deque>
#include <string>

typedef long long ll;

using namespace std;

int n,m,k;
int a[10001];

int main(int argc, char** argv)
{	

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	
	cin >> n >> m >> k;
	for(int i=1; i<=n; i++)
		cin >> a[i];

	vector<set<int>*> sets(n+1);

	for(int i=1; i<=n; i++){
		sets[i] = new set<int>;
		sets[i]->insert(i);
	}
	
	for(int i=0; i<m; i++){
		int v,w;
		cin >> v >> w;

		if(!(sets[v]->find(w) == sets[v]->end())){
			continue;
		}
	
		for(auto iter = sets[w]->begin(); iter != sets[w]->end(); iter++){
			sets[v]->insert(*iter);	
			if(*iter != w)
				sets[*iter] = sets[v];		
		}
		sets[w] = sets[v];
		
	}
	
	vector<int> visit(n+1, 0);
	ll sum =0;

	for(int i=1; i<=n; i++){
		if(visit[i]==1) continue;
		
		int money = INT32_MAX;
		for(auto iter = sets[i]->begin(); iter != sets[i]->end(); iter++){
			int vi = *iter;
			visit[vi] = 1;
			money = min(money, a[vi]);
		}
		
		sum += money;
	}

	if(sum >k)
		cout << "Oh no";
	else
		cout << sum;	

	
}