[백준] 14433 한조 대기 중

문제

그랜드마스터 승급까지 1승이 남은 욱제는 끔찍한 광경을 보고야 말았다. 팀원들이 게임을 던지기 시작한 것이다.

그렇게 승급을 포기하려던 찰나, 욱제는 적 팀도 던진다는 사실을 알아챘다! 이제 승부는 미궁 속으로 빠지게 되었다.

한 팀에는 N명의 플레이어가 있고, 각 팀원은 게임을 시작하기 전에 영웅을 한 명 선택한다. 이때 같은 팀에서 여러 명이 한 영웅을 선택할 수는 없다. 게임에는 수많은 영웅이 있고, 그 중 M개의 영웅은 게임의 승패를 결정지을 정도로 구린 영웅이다. 이런 영웅을 선택하는 것을 트롤픽이라고 불린다. (같은 게임이기 때문에 트롤픽의 수 M은 양 팀 모두 동일하다)

양 팀이 모두 게임을 던지자, 즐겜 분위기가 형성되었다. 각 팀원은 M개의 트롤픽 중 자신이 원하는 트롤픽들을 말하고, 자기 팀에서 최대한 많은 팀원이 즐겜을 할 수 있도록 트롤픽을 분배한다. 트롤픽을 하지 못한 팀원은 아쉽지만 힐러를 고르게 된다.

게임은 비슷한 실력의 팀원을 매칭시켜 주기 때문에, 결국 트롤픽을 더 적게 한 팀이 이기게 된다. 각 팀의 팀원들이 고르고 싶어하는 트롤픽의 리스트가 주어질 때, 욱제가 그랜드마스터를 찍을 수 있는지 알아보자. (비기면 점수를 안 주기 때문에 승급 할 수 없으며, 물론 욱제도 게임을 던진다)

 

N명의 플레이어와 M개의 트롤픽의 최대 매칭을 구하는 이분매칭 문제입니다.

두개의 팀에대해 이분매칭을 수행하고, 욱제의 팀에있는 트롤픽이 상대팀보다 적으면 됩니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

int N, M, K1, K2, x, y, v1[301], v2[301], s1[301], s2[301];
vi adj[301], adj2[301];
bool dfs1(int t) {
	if (v1[t])return 0;
	v1[t] = 1;
	for (int r : adj[t]) {
		if (!s1[r] || dfs1(s1[r])) {
			s1[r] = t;
			return 1;
		}
	}
	return 0;
}
bool dfs2(int t) {
	if (v2[t])return 0;
	v2[t] = 1;
	for (int r : adj2[t]) {
		if (!s2[r] || dfs2(s2[r])) {
			s2[r] = t;
			return 1;
		}
	}
	return 0;
}
int main() {
	FAST;
	cin >> N >> M >> K1 >> K2;
	while (K1--) {
		cin >> x >> y;
		adj[x].push_back(y);
	}
	while (K2--) {
		cin >> x >> y;
		adj2[x].push_back(y);
	}
	int cnt1 = 0, cnt2 = 0;
	REP(i, N) {
		mset(v1);
		mset(v2);
		if (dfs1(i))cnt1++;
		if (dfs2(i))cnt2++;
	}
	if (cnt1 < cnt2)cout << "네 다음 힐딱이";
	else cout << "그만 알아보자";
}