백준11409 열혈강호6

작성일 | In

문제 링크

  • http://icpc.me/11409

사용 알고리즘

  • MCMF
  • Network Flow

시간복잡도

  • O(VEf)

풀이

MCMF는 Min Cost Max Flow, 즉 비용을 최소화 시키는 알고리즘입니다. 비용을 최대화 시키기 위해서는 비용에 -1을 곱해주면 됩니다.

당연하게도 최단 경로(최소 비용)은 음의 사이클이 없어야만 유한한 값이 나옵니다.
다행히도, 원래 그래프에는 음의 사이클이 없어도 플로우 진행 도중 나오는 역방향 간선 때문에 음의 사이클이 생길까 걱정하지 않으셔도 됩니다.


  1. 여기서 a가 최단 경로에 포함되었다고 하면, b > a가 성립합니다.
  2. 가중치와 방향을 모두 뒤집으면 -a로 바뀌게 됩니다.
  3. 만약 방향을 뒤집은 뒤에 음의 사이클이 생긴다면 b-a < 0, 즉 b < a가 되기 때문에 모순입니다.

전체 코드

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;
	MCMF flow(1002, 1001, 1002);

	//cout << "init\n";

	for(int i=1; i<=n; i++){
		flow.addEdge(1001, i, 1, 0);
	}
	for(int i=501; i<=500+m; i++){
		flow.addEdge(i, 1002, 1, 0);
	}

	for(int i=1; i<=n; i++){
		int cnt; cin >> cnt;
		for(int j=0; j<cnt; j++){
			int a, b; cin >> a >> b;
			flow.addEdge(i, 500+a, 1, -b);
		}
	}

	cout << -flow.mcmf();
}