백준1420 학교 가지마!

작성일 | In

문제 링크

  • http://icpc.me/1420

사용 알고리즘

  • Network Flow
  • Max Flow
  • Min Cut

풀이

N <= 100이니 플로우를 고민해볼만 합니다.
정점을 몇 개 없애서 A에서 B를 못 가게 할건데, 없애는 정점을 최소화 해야 합니다.
Min Cut 문제라는 것을 알 수 있습니다.

각 격자칸들을 정점이라고 생각하고, 인접한 격자칸을 간선으로 이어준 그래프를 만들어봅시다.
이 문제에서는 간선이 아닌, 정점을 없애야(끊어야) 하기 때문에 정점을 분할해주면 됩니다.

Minimum Vertex Cut 문제로 바뀌게 됩니다.

전체 코드

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

typedef pair<int, int> p;
const int inf = 1e9;

char arr[111][111];
vector<int> g[23232];
int par[23232];
map<p, int> c, f;
int s = -1, t = -1;
int si, sj, ti, tj;

int n, m;

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

int run(){
	int ret = 0;
	while(1){
		memset(par, -1, sizeof par);
		queue<int> q; q.push(s);
		while(q.size()){
			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(par[t] == -1) break;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			f[{a, b}]++;
			f[{b, a}]--;
		}
		ret++;
	}
	return ret;
}

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

	int pv = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> arr[i][j];
			if(arr[i][j] == 'K'){
				s = pv + 1;
				si = i, sj = j;
			}
			if(arr[i][j] == 'H'){
				t = pv;
				ti = i, tj = j;
			}
			pv += 2;
		}
	}

	if(n == 1 && m == 1){
		cout << -1; return 0;
	}
	if(abs(si - ti) + abs(sj - tj) == 1 || s == -1 || t == -1){
		cout << -1; return 0;
	}

	for(int i=0; i<n*m; i++){
		addEdge(2*i, 2*i+1, 1);
	}

	pv = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(i+1 < n && arr[i][j] != '#' && arr[i+1][j] != '#'){
				int nxt = pv + 2 * m;
				addEdge(pv+1, nxt, inf);
				addEdge(nxt+1, pv, inf);
			}
			if(j+1 < m && arr[i][j] != '#' && arr[i][j+1] != '#'){
				int nxt = pv + 2;
				addEdge(pv+1, nxt, inf);
				addEdge(nxt+1, pv, inf);
			}
			pv += 2;
		}
	}

	cout << run();
}