백준11406 책 구매하기2

작성일 | In

문제 링크

  • http://icpc.me/11406

사용 알고리즘

  • Max Flow

풀이

범위 제한과 문제를 대충 보니 플로우 느낌이 나서 그래프를 모델링 하고 최대 유량을 구했습니다.

source와 서점을 간선으로 이어주고, 서점이 갖고 있는 책의 개수만큼 용량을 설정해줍시다.
사람과 sink를 간선으로 이어주고, 사람이 원하는 책의 개수만큼 용량을 설정해줍시다.

서점과 사람을 간선으로 이어주고, 서점이 사람에게 보낼 수 있는 책의 최대만큼 용량을 설정해주고 플로우를 돌려주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

/*
source(s) -> lib(x) -> people(bias+y) -> sink(t)
*/

int n, m;
int bias = 100;
int s = 201, t = 202;

int c[222][222];
int f[222][222];
int par[222];
int flow;
vector<int> g[222];
int ans = 0;

void addEdge(int a, int b){
	g[a].push_back(b);
	g[b].push_back(a);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;

	for(int i=1; i<=n; i++){
		cin >> c[bias+i][t];
		addEdge(bias+i, t);
	}
	for(int i=1; i<=m; i++){
		cin >> c[s][i];
		addEdge(s, i);
	}
	for(int i=1; i<=m; i++){
		for(int j=bias+1; j<=bias+n; j++){
			cin >> c[i][j];
			addEdge(i, j);
		}
	}

	while(1){
		memset(par, -1, sizeof par);
		flow = 1e9+7;
		queue<int> q; q.push(s);
		while(!q.empty()){
			int now = q.front(); q.pop();
			for(auto nxt : g[now]){
				if(par[nxt] == -1 && c[now][nxt] - f[now][nxt] > 0){
					q.push(nxt); par[nxt] = now;
					if(nxt == t) break;
				}
			}
		}
		if(par[t] == -1) break;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			flow = min(flow, c[a][b] - f[a][b]);
		}
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			f[a][b] += flow; f[b][a] -= flow;
		}
		ans += flow;
	}
	cout << ans;
}