from collections import *
def BFS(x):
parent = [-1]*K
dq = deque([0])
while dq:
now = dq.popleft()
for next in range(K):
if (c:=graph[now][next])<0:
c = x
if parent[next]<0 and c-flow[now][next]:
parent[next] = now
if next==N+1:
return parent
dq.append(next)
def solve(x):
global flow
flow = [[0]*K for i in range(K)]
s = 0
while parent:=BFS(x):
now = N+1; f = M
while now:
last = parent[now]
if (c:=graph[last][now])<0:
c = x
f = min(f,c-flow[last][now])
now = last
now = N+1
while now:
last = parent[now]
flow[last][now] += f; flow[now][last] -= f
now = last
s += f
if S==s:
return flow
N = int(input()); M = 1<<14; K = N*2+2
graph = [[0]*K for i in range(K)]
column,row = [[*map(int,input().split())] for i in range(2)]
S = sum(column)
for i in range(1,N+1):
graph[0][i] = column[i-1]
graph[-i][N+1] = row[i-1]
for j in range(1,N+1):
graph[i][-j] = -1
x,c = M,13
while c+1:
if result:=solve(x):
X,Flow = x,result
x -= 1<<c
else:
x += 1<<c
if not c:
if result:=solve(x):
X,Flow = x,result
c -= 1
print(X)
for i in range(1,N+1):
print(*reversed(Flow[i][-N:]))
최대유량 + 이분탐색으로 해결하였다.
풀이를 설명하면,
1. source - 행 - 열 - sink로 이어지는 그래프를 만든다. 이때 source-행, 열-sink의 용량은 각 행,열의 합과 같고 행-열의 용량은 -1로 둔다.
2. solve(x) 함수는 1에서 -1로 둔 용량을 x로 취급하여 최대유량을 찾는 함수이다. 이때 유량이 S (모든 행 또는 모든 열의 합)과 같으면 true, 다르면 false이다.
3. 이분탐색을 통해 solve(x) 함수가 true를 반환하는 가장 작은 x를 찾는다.
오늘의 교훈) 최대유량은 다양한 방식으로 활용할 수 있다.