백준6241 Dining

작성일 | In

문제 링크

  • http://icpc.me/6241

문제 출처

  • 2007 USACO US Open Gold 2번

사용 알고리즘

  • Network Flow
  • Max flow

풀이

만약 문제에서 음료수가 없고, 소와 음식만 주어진다면 이분 매칭으로 풀 수 있습니다.
이 문제는 어떻게 풀어야 할지 생각해봅시다.

소와 음식만 주어졌을 때는 왼쪽에 음식, 오른쪽에 소를 놓고 이분 그래프를 그릴 수 있습니다.
소와 음료수만 주어졌을 때는 왼쪽에 소, 오른쪽에 음식을 놓고 이분 그래프를 그릴 수 있습니다.

그러면 음식, 소, 음료수가 주어질 때는 왼쪽에 음식, 중간에 소, 오른쪽에 음료수를 놓고 Max Flow를 구하면 되겠네요.
단, 소는 한 번만 선택되어야 하니까 소는 정점 분할을 해야합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

int N, F, D; //1~200, 300~400 500~600
const int s = 611, t = 612;

int c[666][666];
int f[666][666];
int lv[666];
int work[666];

vector<int> g[666];

void addEdge(int s, int e, int x = 1){
	g[s].push_back(e); c[s][e] += x;
	g[e].push_back(s);
}

void init(){
	for(int i=1; i<=F; i++) addEdge(s, 300+i);
	for(int i=1; i<=D; i++) addEdge(500+i, t);
	for(int i=1; i<=N; i++) addEdge(2*i, 2*i+1);
}

bool bfs(){
	memset(lv, -1, sizeof lv);
	queue<int> q; q.push(s); lv[s] = 0;
	while(q.size()){
		int now = q.front(); q.pop();
		for(auto nxt : g[now]){
			if(lv[nxt] == -1 && c[now][nxt] - f[now][nxt] > 0){
				lv[nxt] = lv[now] + 1;
				q.push(nxt);
			}
		}
	}
	return lv[t] != -1;
}

int dfs(int now, int tot){
	if(now == t) return tot;
	for(int &i=work[now]; i<g[now].size(); i++){
		int nxt = g[now][i];
		if(lv[nxt] == lv[now] + 1 && c[now][nxt] - f[now][nxt] > 0){
			int fl = dfs(nxt, min(tot, c[now][nxt] - f[now][nxt]));
			if(fl > 0){
				f[now][nxt] += fl;
				f[nxt][now] -= fl;
				return fl;
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> F >> D;
	init();
	for(int i=1; i<=N; i++){
		int ff, dd; cin >> ff >> dd;
		for(int j=1; j<=ff; j++){
			int now; cin >> now;
			addEdge(300+now, i*2);
		}
		for(int j=1; j<=dd; j++){
			int now; cin >> now;
			addEdge(i*2+1, 500+now);
		}
	}

	int ans = 0;
	while(bfs()){
		memset(work, 0, sizeof work);
		while(1){
			int fl = dfs(s, 1e9);
			if(fl <= 0) break;
			ans += fl;
		}
	}

	cout << ans;
}