백준1210 마피아

작성일 | In

문제 링크

  • http://icpc.me/1210

문제 출처

  • 2008 BalticOI Day2 3번

사용 알고리즘

  • Network Flow
  • Min Cut
  • Max Flow
  • BFS

풀이

톨게이트를 정점, 도로를 간선이라고 두고 그래프를 만들어봅시다.
문제에서 톨게이트를 막으라고 했기 때문에 Minimum Vertex Cut을 생각해볼 수 있습니다.
일단 정점 분할을 하고 플로우를 돌려서 Minimum Vertex Cut을 구합시다.

이제 막아야 하는 톨게이트 번호를 구해야 합니다.
Source에서 시작해 용량이 남은 간선만을 이용해 BFS를 돌려줍시다.
정점 V를 분할한 두 정점을 inV와 outV라고 할 때, inV는 방문할 수 있고 outV는 방문할 수 없다면 V를 막아야 합니다.

전체 코드

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

int c[444][444];
int f[444][444];
vector<int> g[444];
int s, t;
int lv[444];
int work[444];
int chk[444];

const int inf = 1e9;

int n, m;

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

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 dinic(){
	int ret = 0;
	while(bfs()){
		memset(work, 0, sizeof work);
		while(1){
			int fl = dfs(s, inf+10);
			if(fl <= 0) break;
			ret += fl;
		}
	}
	return ret;
}

void solve(){
	dinic();
	queue<int> q; q.push(s); chk[s] = 1;
	while(q.size()){
		int now = q.front(); q.pop();
		for(auto nxt : g[now]){
			if(chk[nxt]) continue;
			if(c[now][nxt] - f[now][nxt] > 0){
				q.push(nxt); chk[nxt] = 1;
			}
		}
	}

	for(int i=1; i<=n; i++){
		if(chk[i] && !chk[i+n]) cout << i << " ";
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	cin >> s >> t; t += n;
	for(int i=1; i<=n; i++){
		int x; cin >> x;
		addEdge(i, i+n, x);
	}
	for(int i=1; i<=m; i++){
		int a, b; cin >> a >> b;
		addEdge(a+n, b);
		addEdge(b+n, a);
	}
	solve();
}