백준 알고리즘 2188번 문제 : 축사배정

문제는 백준 사이트에서 확인하세요!

 

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

2188번: 축사 배정

오늘 포스팅할 문제는 최대 유량과 관련된 문제입니다.

 

milk scheduling 문제를 풀때도 그랬지만 John씨는 참 훌륭한 농부 같군요.

문제분석

농부 John씨는 축사를 n칸으로 구분하고, 하나의 칸에 하나의 소만 들어가길 원합니다.

 

아쉽게도 소들의 취향이 정해져있어서 원하는 칸에 들어가지 못하면 거부한다네요.

 

훌륭한 농부 John씨는 소들의 취향을 고려해서 소가 들어가길 원하는 축사 리스트를 바탕으로

 

축사 한칸에 소 한마리씩 배치하려 합니다.

 

이때 축사에 들어갈 수 있는 소들의 최대값을 구하는 문제입니다.

 

소와 축사 간에는 이런 관계가 있다고 볼 수 있네요.

 

소가 어떤 축사 칸에 들어가면 나머지 소는 그 칸에 들어갈 수 없습니다.

 

이것을 최대 유량 문제로 나타내면 축사 칸 하나당 1의 capacity를 갖고,

 

소가 축사에 들어가는 것은 유량으로 표현할 수 있습니다.

 

문제의 예시를 유량 그래프로 나타낸 것입니다. 모든 간선의 flow는 0이고, capacity는 1입니다.

 

한개의 유량이 s에서 소를 지나고 축사를 거쳐 t에 도달하면 경로에 놓인 간선은  1 / 1 이 되므로

 

residual capacity는 0이 됩니다. 따라서 출발지에서 해당 경로를 더이상 쓸 수 없게 됩니다.

 

자연스럽게 다른 경로를 선택합니다! ^^

 

문제 해결

 

먼저 소의 취향 정보를 인접리스트로 나타냅니다.

 

그 후 소와 축사 칸의 개수를 유량 네트워크로 표현한 다음 ford-fulkerson 알고리즘을 이용하면

이 문제를 해결할 수 있습니다!

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

bool dfs(int s, int t);
int ford_fulkerson(int s, int t);
vector<bool> visit;
vector<vector<int>> f, c;
int n, m, t;

int main() {
	int tm, tc;

	cin >> n >> m;
	t = n + m + 1;
	f = c = vector<vector<int>>( t + 1, vector<int>(t + 1, 0));
	
	for (int i = 1; i <= n; i++) {
		c[0][i] = 1;
		cin >> tm;
		for(int j=1; j<=tm; j++){
			cin >> tc;
			c[i][n + tc] = 1;
			c[n + tc][t] = 1;
		}
	}
	cout << ford_fulkerson(0,t) << endl;
}

int ford_fulkerson(int s, int t) {
	int ans = 0;
	visit.resize(t + 1);
	for (int i = 0; i <= t; i++) {
		visit[i] = false;
	}

	while (dfs(s, t)) {
		ans ++;

		for (int i = 0; i <= t; i++) {
			visit[i] = false;
		}
	}

	return ans;
}

bool dfs(int s, int t) {
	visit[s] = true;
	if (s == t) {
		return true;
	}

	for (int i = 1; i <= t; i++) {
		if (visit[i] == false && c[s][i] > f[s][i]) {
			if (dfs(i,t)) {
				f[s][i] ++;
				f[i][s] --;
				return true;
			}
		}
	}
	return false;
}