BOJ 1210 마피아 (Python)

접근

3번째 조건 우리의 점거된 톨게이트를 지나지 않고서는 을 보았을 때 최대유량의 최소컷 정리를 떠올릴 수 있었다.

최소컷 정리에 의하여 그래프 노드가 Source쪽과 Sink쪽으로 나눠 질 수 있는 후보군들을 찾으면 된다.

양방향 간선이므로 정점 분할을 해주고 최대유량을 흘려보내준다.

이후에는 들어올 순 있지만 나갈수는 없는 간선 즉, bfs를 통해 Source로부터 시작하였을 때 check[i]는 가능하지만 check[n+i]는 불가능한 톨게이트 번호를 뽑아준다.

code


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
 import sys
from collections import deque
input = sys.stdin.readline

def bfs() :
    global level
    q = deque([source])
    level = [-1 for _ in range(k)]
    level[source] = 0

    while q :
        x = q.popleft()
        for nx in g[x] :
            if c[x][nx] - f[x][nx] > 0 and level[nx] == -1 :
                level[nx] = level[x] + 1
                q.append(nx)
    
    return level[sink] != -1

def dfs(x, flow) :
    if x == sink :
        return flow
    
    while work[x] < len(g[x]) :
        nx = g[x][work[x]]
        if c[x][nx] - f[x][nx] > 0 and level[x] + 1 == level[nx] :
            min_flow = dfs(nx, min(flow, c[x][nx] - f[x][nx]))
            if min_flow :
                f[x][nx] += min_flow
                f[nx][x] -= min_flow
                return min_flow
        work[x] += 1
    return 0

n, m = map(int,input().split())
s, e = map(int,input().split())
cost = [int(input()) for _ in range(n)]
k = n*2 + 4; sink = k-1; source = k-2

g = [[] for _ in range(k)]
c = [[0 for _ in range(k)] for _ in range(k)]
f = [[0 for _ in range(k)] for _ in range(k)]
level = [-1 for _ in range(k)]
work = [0 for _ in range(k)]

g[source].append(s); 
g[s].append(source)
c[source][s] = 1e9

g[n+e].append(sink); 
g[sink].append(n+e)
c[n+e][sink] = 1e9

for i in range(1, n+1) :
    g[i].append(i+n)
    g[i+n].append(i)
    c[i][i+n] = cost[i-1]

for _ in range(m):
    a, b = map(int, input().split())
    g[a+n].append(b)
    g[b].append(a+n)
    c[a+n][b] = 1e9
    
    g[b+n].append(a)
    g[a].append(b+n)
    c[b+n][a] = 1e9


while bfs() :
    ans = 0
    work = [0 for _ in range(k)]
    while True :
        mf = dfs(source, 1e12)
        if not mf :
            break
        ans += mf

check = [False for _ in range(k)]
q = deque([source])
check[source] = True

while q :
    x = q.popleft()
    for nx in g[x] :
        if c[x][nx] - f[x][nx] > 0 and not check[nx] :
            check[nx] = True
            q.append(nx)

result = []
for i in range(1, n+1) :
    if check[i] and not check[n+i] :
        result.append(i)
print(*result)

접근

code

Enjoy Reading This Article?