実は、「$1～N$ の数字が $M$ 個ずつ配置されている」という条件を満たしていれば必ず可能であり、
その証明があれば、1列ずつ貪欲に決めていってもいい、という考え方となる。
（入力サンプルにも可能な例しか無かった時点で少し怪しかったね）
from collections import deque
from typing import Tuple, List
class Dinic:
"""
Usage:
mf = Dinic(n)
-> mf.add_link(from, to, capacity)
-> mf.max_flow(source, target)
"""
def __init__(self, n: int):
self.n = n
self.links: List[List[List[int]]] = [[] for _ in range(n)]
# if exists an edge (v→u, capacity)...
# links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]
def add_link(self, from_: int, to: int, capacity: int) -> None:
self.links[from_].append([capacity, to, len(self.links[to]), 1])
self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])
def bfs(self, s: int) -> List[int]:
depth = [-1] * self.n
depth[s] = 0
q = deque([s])
while q:
v = q.popleft()
for cap, to, rev, _ in self.links[v]:
if cap > 0 and depth[to] < 0:
depth[to] = depth[v] + 1
q.append(to)
return depth
def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
links = self.links
stack = [s]
while stack:
v = stack[-1]
if v == t:
break
for i in range(progress[v], link_counts[v]):
progress[v] = i
cap, to, rev, _ = links[v][i]
if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
continue
stack.append(to)
break
else:
progress[v] += 1
stack.pop()
else:
return 0
f = 1 << 60
fwd_links = []
bwd_links = []
for v in stack[:-1]:
cap, to, rev, _ = link = links[v][progress[v]]
f = min(f, cap)
fwd_links.append(link)
bwd_links.append(links[to][rev])
for link in fwd_links:
link[0] -= f
for link in bwd_links:
link[0] += f
return f
def max_flow(self, s: int, t: int) -> int:
link_counts = list(map(len, self.links))
flow = 0
while True:
depth = self.bfs(s)
if depth[t] < 0:
break
progress = [0] * self.n
current_flow = self.dfs(s, t, depth, progress, link_counts)
while current_flow > 0:
flow += current_flow
current_flow = self.dfs(s, t, depth, progress, link_counts)
return flow
def cut_edges(self, s: int) -> List[Tuple[int, int]]:
""" max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
q = [s]
reachable = [0] * self.n
reachable[s] = 1
while q:
v = q.pop()
for cap, u, li, _ in self.links[v]:
if cap == 0 or reachable[u]:
continue
reachable[u] = 1
q.append(u)
edges = []
for v in range(self.n):
if reachable[v] == 0:
continue
for cap, u, li, orig in self.links[v]:
if orig == 1 and reachable[u] == 0:
edges.append((v, u))
return edges
n, m = map(int, input().split())
s = 2 * n
t = s + 1
ans = [[0] * m for _ in range(n)]
count_by_col = [[0] * n for _ in range(n)] # i 行目にある数字 k の個数
fixed_by_col = [[0] * n for _ in range(n)] # 1列ずつ決める過程で、i 行目に数字 k が埋まった個数
field = []
for i in range(n):
row = list(map(int, input().split()))
for j in range(m):
row[j] -= 1
count_by_col[i][row[j]] += 1
field.append(row)
for j in range(m):
dnc = Dinic(t + 1)
for i in range(n):
for k in range(n):
rem = count_by_col[i][k] - fixed_by_col[i][k]
if rem:
dnc.add_link(i, k + n, 1)
dnc.add_link(s, i, 1)
dnc.add_link(i + n, t, 1)
result = dnc.max_flow(s, t)
if result < n:
print('No')
exit()
for i in range(n):
for link in dnc.links[i]:
if link[3] == 1 and link[0] == 0:
k = link[1] - n
ans[i][j] = k + 1
fixed_by_col[i][k] += 1
print('Yes')
for row in ans:
print(' '.join(map(str, row)))