[BOJ 1031] 스타 대결

문제

---

https://www.acmicpc.net/problem/1031

풀이

---

지민이 팀의 팀원 N명과 한수 팀의 팀원 M명을 각각 노드로 만들어주고, 지민이 팀은 source와, 한수 팀은 sink와 이어준다.

이때 각 엣지의 capacity는 해야 하는 경기의 수이다.

그 후 N * M개의 (지민 팀 팀원, 한수 팀 팀원) 엣지를 capacity 1로 이어준다.

그 후 최대 flow를 구해, 총 경기 수와 다르면 -1을 출력한다.

같다면, 완전 중요한 간선에서 사용한 테크닉을 이용한다.

flow 1이 흐르는 (지민 팀 팀원, 한수 팀 팀원) 엣지에 대해, 이 간선이 완전 중요한 간선인지 판단하는 것이다.

완전 중요한 간선이 아니면서, 동시에 사전 순으로 더 앞서는 대진표로 바꿀 수 있다면 바꾼다.

그렇게 하기 위해서는, (지민 팀의 i번째 팀원) 노드에서 (한수 팀의 j번째 팀원) 노드로 가는 경로를 bfs로 찾을 때,

1. 맨 처음 deque에 (지민 팀의 i번째 팀원, 한수 팀의 k번째 팀원) 엣지를 모두 넣는다. 물론 이 엣지의 현재 flow는 0이어야 하고, k는 j보다 커야 한다.

2. bfs를 돌릴 때, 현재 위치가 지민 팀의 노드라면, 한수 팀의 노드들 중 현재 flow가 0인 노드들을 모두 deque에 넣는다.

3. 현재 위치가 한수 팀의 노드라면, 지민 팀의 k번째 팀원 노드를 deque에 넣는다. 이때 둘을 잇는 엣지의 현재 flow는 0이고, k는 i보다 크다.

1, 3번의 제약으로 인해 사전 순으로 더 앞서는 형태로만 변환됨이 보장된다.

그렇게 (지민 팀의 i번째 팀원, 한수 팀의 j번째 팀원) 엣지를 대체할 수 있는 우회 경로를 찾으면 이에 따라 graph를 전부 갱신해 준다.

코드

---

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
col = list(map(int, sys.stdin.readline().split()))
row = list(map(int, sys.stdin.readline().split()))

graph = [[0] * (n + m + 2) for _ in range(n + m + 2)]

for i in range(n):
    graph[0][i + 1] = col[i]

for j in range(m):
    graph[n + j + 1][-1] = row[j]

for i in range(1, n + 1):
    for j in range(n + 1, n + m + 1):
        graph[i][j] = 1

ans = 0
while True:
    prev = [-1] * (n + m + 2)
    queue = deque([0])
    while queue:
        cur = queue.popleft()
        
        if cur == 0:
            for nxt in range(n, 0, -1):
                if (prev[nxt] == -1) and graph[cur][nxt]:
                    prev[nxt] = cur
                    queue.append(nxt)
        
        elif cur <= n:
            for nxt in range(n + m, n, -1):
                if (prev[nxt] == -1) and graph[cur][nxt]:
                    prev[nxt] = cur
                    queue.append(nxt)
        
        else:
            if graph[cur][-1]:
                prev[-1] = cur
                break
            
            for nxt in range(n, 0, -1):
                if (prev[nxt] == -1) and graph[cur][nxt]:
                    prev[nxt] = cur
                    queue.append(nxt)

        if prev[-1] != -1:
            break
    
    if prev[-1] == -1:
        break

    ans += 1
    nxt = -1
    while nxt:
        cur = prev[nxt]
        graph[cur][nxt] -= 1
        graph[nxt][cur] += 1
        nxt = cur

if ans == sum(row):
    for i in range(1, n + 1):
        for j in range(n + 1, n + m + 1):
            if graph[i][j] == 0:
                prev = [-1] * (n + m + 2)
                
                queue = deque()
                for nxt in range(n + m, j, -1):
                    if graph[i][nxt]:
                        prev[nxt] = i
                        queue.append(nxt)
                
                while queue:
                    cur = queue.popleft()

                    if 1 <= cur <= n:
                        for nxt in range(n + m, n, -1):
                            if (prev[nxt] == -1) and graph[cur][nxt]:
                                prev[nxt] = cur
                                queue.append(nxt)
                    
                    else:
                        for nxt in range(n, i, -1):
                            if (prev[nxt] == -1) and graph[cur][nxt]:
                                prev[nxt] = cur
                                queue.append(nxt)
                    
                    if prev[j] != -1:
                        break
                
                if prev[j] != -1:
                    graph[i][j] += 1
                    graph[j][i] -= 1
                    nxt = j
                    while True:
                        cur = prev[nxt]
                        graph[cur][nxt] -= 1
                        graph[nxt][cur] += 1
                        nxt = cur
                        if nxt == i:
                            break

    for i in range(1, n + 1):
        for j in range(n + 1, n + m + 1):
            print(graph[j][i], end='')
        print()
else:
    print(-1)