문제

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


알고리즘

이분 매칭


풀이

두 가지의 풀이가 있습니다. 1번 풀이는 정점분할입니다. 사람정점 $i$번에 대해 $T(i)$,$F(i)$ 이와 같이 두가지의 정점으로 나눈후 열혈강호 1과 동일하게 풀면 됩니다. 2번 풀이는 사람정점 $i$번에 대해 dfs를 두 번 수행하는 것입니다. 그럼 한 사람당 최대 두가지 일에 매칭이 되어 문제를 해결할 수 있습니다.

코드1

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

#define T(x) (x<<1)
#define F(x) (x<<1|1)

const int MAX_N = 2002;
int N, M,cnt,v;

vector<vector<int>> adj;
bool visited[MAX_N];
int match[MAX_N];

bool dfs(int here) {
	visited[here] = true;
	for (auto there : adj[here]) {
		int u = match[there];
		if (!u || !visited[u] && dfs(u)) {
			match[there] = here;
			return true;
		}
	}
	return false;
}

int bipartite_matching() {
	int ret = 0;
	for(int i=T(1);i<=F(N);++i) {
		memset(visited, 0, sizeof(visited));
		if (dfs(i)) ++ret;
	}
	return ret;
}

int main() {
	FAST;
	cin >> N >> M;
	adj.resize(2*(N + 1));
	REP(i, N) {
		cin >> cnt;
		while (cnt--) {
			cin >> v;
			adj[T(i)].emplace_back(v);
			adj[F(i)].emplace_back(v);
		}
	}
	cout << bipartite_matching();
	return 0;
}

코드2

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M,cnt,w;

vector<vector<int>> adj;
int match[1001];
bool visited[1001];

bool dfs(int here) {
	visited[here] = true;
	for (auto there : adj[here]) {
		int u = match[there];
		if (!u || !visited[u] && dfs(u)) {
			match[there] = here;
			return true;
		}
	}
	return false;
}

int bipartite_matching() {
	int ret = 0;
	REP(i, N) {
		memset(visited, 0, sizeof(visited));
		if (dfs(i)) ++ret;
		memset(visited, 0, sizeof(visited));
		if (dfs(i)) ++ret;
	}
	return ret;
}

int main() {
	FAST;
	cin >> N >> M;
	adj.resize(N + 1);
	REP(i, N) {
		cin >> cnt;
		while (cnt--) {
			cin >> w;
			adj[i].emplace_back(w);
		}
	}
	cout << bipartite_matching();
	return 0;
}