백준11407 책 구매하기3

작성일 | In

문제 링크

  • http://icpc.me/11407

사용 알고리즘

  • MCMF

풀이

source와 서점을 cost가 0인 간선으로 이어줍니다. 용량은 서점이 갖고 있는 책의 개수가 됩니다.
사람과 sink를 cost가 0인 간선으로 이어줍니다. 용량은 사람이 구매하고 싶은 책의 개수가 됩니다.
서점과 사람을 간선으로 이어줍니다. 용량은 Ci,j가 되고, 비용은 Di,j가 됩니다.

MCMF를 돌려주면 됩니다.

전체 코드

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

int bias = 100;
int f[222][222];
int c[222][222];
int d[222][222];
vector<int> g[222];
int par[222];
int dist[222];
int inque[222];
int match = 0, cost = 0;

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

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

	for(int i=bias+1; i<=bias+n; i++){
		cin >> c[i][t]; d[i][t] = 0;
		g[i].push_back(t);
		g[t].push_back(i);
	}
	for(int i=1; i<=m; i++){
		cin >> c[s][i]; d[s][i] = 0;
		g[s].push_back(i);
		g[i].push_back(s);
	}

	for(int i=1; i<=m; i++){
		for(int j=bias+1; j<=bias+n; j++){
			cin >> c[i][j];
			g[i].push_back(j);
			g[j].push_back(i);
		}
	}
	for(int i=1; i<=m; i++){
		for(int j=bias+1; j<=bias+n; j++){
			cin >> d[i][j]; d[j][i] = -d[i][j];
		}
	}

	while(1){
		memset(par, -1, sizeof par);
		memset(dist, 0x3f, sizeof dist);
		memset(inque, 0, sizeof inque);
		queue<int> q; q.push(s);
		inque[s] = 1; dist[s] = 1;

		while(!q.empty()){
			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];
					par[nxt] = now;
					if(!inque[nxt]){
						q.push(nxt); inque[nxt] = 1;
					}
				}
			}
		}

		if(par[t] == -1) break;
		int flow = 1e9+7;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			flow = min(flow, c[a][b] - f[a][b]);
		}
		match += flow;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			f[a][b] += flow; f[b][a] -= flow;
			cost += flow * d[a][b];
		}
	}
	cout << match << "\n" << cost;
}