취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14433번 문제인 한조 대기 중이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/14433 

각 팀마다 "선수"와 "트롤픽"을 각각 노드로 하는 이분그래프를 만들어 최대 매칭을 구해 비교하는 문제이다.

각 팀별 최대 이분매칭을 구할 때 그래프 등의 초기화에 유의하자.

아래는 제출한 소스코드이다.

#define NODE 301
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
vector<int> G[NODE];
int visited[NODE];
int matching[NODE];

int bpfunc(int current) {
	if (visited[current]) return 0;
	visited[current] = 1;
	for (auto& node : G[current]) {
		if (matching[node] == 0) {
			matching[node] = current;
			return 1;
		}
		if (bpfunc(matching[node])) {
			matching[node] = current;
			return 1;
		}
	}
	return 0;
}

int bipartitematching() {
	int ret = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, 0, sizeof(visited));
		ret += bpfunc(i);
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int match1, match2;

	int M, K1, K2; cin >> N >> M >> K1 >> K2;
	while (K1--) {
		int i, j; cin >> i >> j;
		G[i].emplace_back(j);
	}
	match1 = bipartitematching();

	for (auto& v : G) v.clear();
	memset(matching, 0, sizeof(matching));

	while (K2--) {
		int i, j; cin >> i >> j;
		G[i].emplace_back(j);
	}
	match2 = bipartitematching();

	if (match1 < match2) cout << "네 다음 힐딱이";
	else cout << "그만 알아보자";
}