백준11405 책 구매하기

작성일 | In

문제 링크

  • http://icpc.me/11405

사용 알고리즘

  • MCMF
  • Network Flow

풀이

i번째 서점은 Bi개의 책을 갖고 시작합니다. 그러므로 source부터 i번 서점까지 용량이 Bi인 간선으로 연결해줍시다.
같은 방법으로, i번째 사람은 Ai개의 책을 구매하기를 원합니다. 그러므로 i번 사람부터 sink까지 용량이 Ai인 간선으로 연결해줍시다.

i번 서점에서 j번 사람까지는 용량이 inf이고, 비용은 Cij인 간선으로 연결해주면 됩니다.

전체 코드

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

struct MCMF{
	int n;
	int c[1010][1010] = {0}; //capacity
	int f[1010][1010] = {0}; //flow
	int d[1010][1010] = {0}; //dist
	vector<int> g[1010]; //graph
	int source, sink;

	MCMF(){
		init(n);
	}

	MCMF(int n, int s, int t){
		init(n);
		source = s, sink = t;
	}

	void init(int _n){
		n = _n+1;
		source = sink = -1;
		memset(c, 0, sizeof c);
		memset(d, 0, sizeof d);
		memset(f, 0, sizeof f);
	}

	void setSource(int s){
		source = s;
	}

	void setSink(int t){
		sink = t;
	}

	void addEdge(int s, int e, int cap, int dist){
		g[s].push_back(e); c[s][e] = cap; d[s][e] = dist;
		g[e].push_back(s); c[e][s] = 0; d[e][s] = -dist;
	}

	int mcmf(){
		//int cnt = 0;
		int minCost = 0;
		int prv[1010], dist[1010];
		bool inque[1010] = {0};
		while(1){
			memset(prv, -1, sizeof prv); memset(dist, 0x3f, sizeof dist); memset(inque, 0, sizeof inque);
			queue<int> q;
			dist[source] = 0;
			inque[source] = 1;
			q.push(source);

			while(q.size()){
				int now = q.front(); q.pop(); inque[now] = 0;
				for(auto nxt : g[now]){
					if(c[now][nxt] - f[now][nxt] > 0 && dist[nxt] > dist[now] + d[now][nxt]){
						dist[nxt] = dist[now] + d[now][nxt];
						prv[nxt] = now;
						if(!inque[nxt]){
							q.push(nxt);
							inque[nxt] = 1;
						}
					}
				}
			}
			if(prv[sink] == -1) break;
			int flow = 1e9+7;
			for(int i=sink; i!=source; i=prv[i]){
				flow = min(flow, c[prv[i]][i] - f[prv[i]][i]);
			}
			for(int i=sink; i!=source; i=prv[i]){
				minCost += flow * d[prv[i]][i];
				f[prv[i]][i] += flow;
				f[i][prv[i]] -= flow;
			}
			//cnt++;
		}
		//cout << cnt << "\n";
		return minCost;
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;
	int s = 1001, t = 1002;
	MCMF flow(1002, s, t);

	for(int i=1; i<=n; i++){
		int a; cin >> a;
		flow.addEdge(100+i, t, a, 0);
	}
	for(int i=1; i<=m; i++){
		int a; cin >> a;
		flow.addEdge(s, i, a, 0);
	}

	for(int i=1; i<=m; i++){
		for(int j=101; j<=100+n; j++){
			int a; cin >> a;
			flow.addEdge(i, j, 1e9+7, a);
		}
	}

	cout << flow.mcmf();
}