Algorithm/BOJ
학교 가지마! - 1420
jhg0406
2020. 2. 12. 18:32
|
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
//1420 - 학교가지마!
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 2000000000
int N, M;
vector<vector<char>> arr;
int source, sink;
int xarr[4] = {1, -1, 0, 0};
int yarr[4] = {0, 0, 1, -1};
struct Edge
{
int target, capa, flow;
Edge *oppo;
int residualCapa()
{
if (capa == INF)
return INF;
return capa - flow;
}
void push(int amt)
{
flow += amt;
oppo->flow -= amt;
}
};
vector<vector<Edge *>> adj;
void addEdge(int u, int v, int capa)
{
Edge *uv = new Edge();
Edge *vu = new Edge();
uv->target = v;
uv->capa = capa;
uv->flow = 0;
uv->oppo = vu;
vu->target = u;
vu->capa = 0;
vu->flow = 0;
vu->oppo = uv;
adj[u].push_back(uv);
adj[v].push_back(vu);
}
void init()
{
cin >> N >> M;
arr = vector<vector<char>>(N, vector<char>(M));
adj = vector<vector<Edge *>>(2 * N * M);
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
{
cin >> arr[i][j];
if (arr[i][j] == 'K')
source = i * M + j + N * M;
else if (arr[i][j] == 'H')
sink = i * M + j;
}
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (arr[i][j] != '#')
{
int sidx = i * M + j;
int eidx = sidx + N * M;
for (int k = 0; k < 4; ++k)
if (i + xarr[k] >= 0 && i + xarr[k] < N && j + yarr[k] >= 0 && j + yarr[k] < M && arr[i + xarr[k]][j + yarr[k]] != '#')
{
addEdge(eidx, (i + xarr[k]) * M + j + yarr[k], INF);
addEdge((i + xarr[k]) * M + j + yarr[k] + N * M, sidx, INF);
}
}
for (int i = 0; i < N * M; ++i)
addEdge(i, i + N * M, 1);
}
int networkFlow(int source, int sink)
{
int totalFlow = 0;
while (true)
{
queue<int> q;
vector<int> parent(2 * M * N, -1);
vector<int> pidx(2 * M * N);
parent[source] = source;
q.push(source);
while (!q.empty() && parent[sink] == -1)
{
int here = q.front();
q.pop();
for (int i = 0; i < adj[here].size(); ++i)
{
if (parent[adj[here][i]->target] == -1 && adj[here][i]->residualCapa() > 0)
{
q.push(adj[here][i]->target);
parent[adj[here][i]->target] = here;
pidx[adj[here][i]->target] = i;
}
}
}
if (parent[sink] == -1)
break;
for (int p = sink; p != source; p = parent[p])
adj[parent[p]][pidx[p]]->push(1);
totalFlow += 1;
}
return totalFlow;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
init();
int t = source - N * M - sink;
if (t == M || t == -M)
cout << -1;
else if (sink / M == (source - N * M) / M)
{
if (t == -1 || t == 1)
cout << -1;
else
cout << networkFlow(source, sink);
}
else
cout << networkFlow(source, sink);
}
|
cs |
https://www.acmicpc.net/problem/1420
1420번: 학교 가지마!
첫째 줄에 도시의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 100) 둘째 줄부터 N개의 줄에 도시의 모양이 주어진다. 비어있으면 점('.'), 벽은 '#', 도현이의 위치는 K, 학교의 위치는 H이다. K와 H는 하나만 주어진다.
www.acmicpc.net
학교 가지마!
정점을 끊는 최소 컷 문제입니다!
최대유량 최소컷 정리에 의해 최대유량 알고리즘으로 해결가능 합니다.
정점에 대해 끊어야 하니 하나의 정점을 2개의 정점으로 나누어 표현합니다.
(들어오는 정점, 나가는 정점)
K, H가 붙어있는 경우는 -1을 출력해야 하니 따로 예외처리를 해주었습니다.
