백준 11376 열혈강호 2 (c++) : 피너클

11376번: 열혈강호 2

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

 

이분매칭 문제다.

이분 매칭이 무엇인지는 다른 곳에서 보고오길 바란다.

 

이 문제에서 헷갈리는것은 한 사람이 2개의 일을 할 수 있다는 것이다.

bool dfs(int person) {
	if (visited[person]) return false;
	visited[person] = true;

	for (int i = 0; i < graph[person].size(); i++) {
		int job = graph[person][i];

		if (match[job] == -1 || dfs(match[job])) {
			match[job] = person;
			return true;
		}
	}
	return false;
}

 

내가 사용한 이분 매칭 알고리즘이다.

 

person이 들어오면 person이 할수있는 일들을 확인하며 

job (할수있는일)에 매칭된 사람이 없거나 match[job] (job에 매칭된 사람) 이 다른 일을 할 수 있으면 true를 반환한다.

 

결국 dfs는 일에 사람이 매칭되면 true를 반환한다.

 

	for (int i = 1; i <= n; i++) {
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < 1001; j++) visited[j] = false;
			if (dfs(i)) ans++;
		}
	}

결국 간단하다. 이분 매칭을 두번 돌려주면 된다.

 

dfs는 person이 할 수 있는 일을 전부 하나씩 다 확인 한다.

한번 돌리면 일을 하나 하는거고 두번 돌리면 일을 두번 하는것이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector<int> graph[1001];
bool visited[1001];
int match[1001];

bool dfs(int person) {
	if (visited[person]) return false;
	visited[person] = true;

	for (int i = 0; i < graph[person].size(); i++) {
		int job = graph[person][i];

		if (match[job] == -1 || dfs(match[job])) {
			match[job] = person;
			return true;
		}
	}
	return false;
}

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a;
		for (int j = 0; j < a; j++) {
			cin >> b;
			graph[i].push_back(b);
		}
	}

	int ans = 0;
	for (int i = 0; i < 1001; i++) match[i] = -1;

	for (int i = 1; i <= n; i++) {
		for (int k = 0; k < 2; k++) {
			for (int j = 0; j < 1001; j++) visited[j] = false;
			if (dfs(i)) ans++;
		}
	}
	cout << ans << '\n';


	return 0;
}

전체코드다.