結果
| 問題 |
No.2328 Build Walls
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-04-16 16:39:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,937 bytes |
| コンパイル時間 | 487 ms |
| コンパイル使用メモリ | 81,532 KB |
| 実行使用メモリ | 595,052 KB |
| 最終ジャッジ日時 | 2025-04-16 16:40:47 |
| 合計ジャッジ時間 | 6,002 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 MLE * 1 -- * 23 |
ソースコード
import sys
from collections import deque
class Edge:
def __init__(self, to, rev, capacity):
self.to = to
self.rev = rev
self.capacity = capacity
class Dinic:
def __init__(self, n):
self.size = n
self.graph = [[] for _ in range(n)]
def add_edge(self, fr, to, cap):
forward = Edge(to, len(self.graph[to]), cap)
backward = Edge(fr, len(self.graph[fr]), 0)
self.graph[fr].append(forward)
self.graph[to].append(backward)
def bfs_level(self, s, t, level):
q = deque()
level[:] = [-1] * self.size
level[s] = 0
q.append(s)
while q:
v = q.popleft()
for edge in self.graph[v]:
if edge.capacity > 0 and level[edge.to] == -1:
level[edge.to] = level[v] + 1
q.append(edge.to)
if edge.to == t:
return
return
def dfs_flow(self, v, t, flow, level, ptr):
if v == t:
return flow
while ptr[v] < len(self.graph[v]):
edge = self.graph[v][ptr[v]]
if edge.capacity > 0 and level[v] < level[edge.to]:
min_flow = min(flow, edge.capacity)
result = self.dfs_flow(edge.to, t, min_flow, level, ptr)
if result > 0:
edge.capacity -= result
self.graph[edge.to][edge.rev].capacity += result
return result
ptr[v] += 1
return 0
def max_flow(self, s, t):
flow = 0
level = [-1] * self.size
INF = float('inf')
while True:
self.bfs_level(s, t, level)
if level[t] == -1:
return flow
ptr = [0] * self.size
while True:
f = self.dfs_flow(s, t, INF, level, ptr)
if f == 0:
break
flow += f
level = [-1] * self.size
return flow
def main():
H, W = map(int, sys.stdin.readline().split())
grid = []
for _ in range(H-2):
grid.append(list(map(int, sys.stdin.readline().split())))
INF = 1 << 60
S = 0
T = 1
row1_nodes = W
rowH_nodes = W
rows_middle = (H-2)*W*2
total_nodes = 2 + row1_nodes + rowH_nodes + rows_middle
dinic = Dinic(total_nodes)
def get_row1_node(j):
return 2 + j
def get_rowH_node(j):
return 2 + row1_nodes + j
def get_in_node(i, j):
offset = 2 + row1_nodes + rowH_nodes
i_in_middle = i - 2
return offset + i_in_middle * 2 * W + j * 2
def get_out_node(i, j):
return get_in_node(i, j) + 1
for j in range(W):
dinic.add_edge(S, get_row1_node(j), INF)
for j in range(W):
dinic.add_edge(get_rowH_node(j), T, INF)
for code_row in range(H-2):
problem_row = 2 + code_row
for code_col in range(W):
j = code_col
a = grid[code_row][code_col]
in_node = get_in_node(problem_row, j)
out_node = get_out_node(problem_row, j)
if a == -1:
cap = INF
else:
cap = a
dinic.add_edge(in_node, out_node, cap)
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
for problem_row in range(1, H+1):
for j in range(W):
current_j = j
if problem_row == 1:
current_node = get_row1_node(current_j)
for di, dj in dirs:
ni = problem_row + di
nj = current_j + dj
if 1 <= ni <= H and 0 <= nj < W:
if ni == 1:
next_node = get_row1_node(nj)
dinic.add_edge(current_node, next_node, INF)
elif ni == H:
next_node = get_rowH_node(nj)
dinic.add_edge(current_node, next_node, INF)
else:
next_in_node = get_in_node(ni, nj)
dinic.add_edge(current_node, next_in_node, INF)
elif problem_row == H:
current_node = get_rowH_node(current_j)
for di, dj in dirs:
ni = problem_row + di
nj = current_j + dj
if 1 <= ni <= H and 0 <= nj < W:
if ni == 1:
next_node = get_row1_node(nj)
dinic.add_edge(current_node, next_node, INF)
elif ni == H:
next_node = get_rowH_node(nj)
dinic.add_edge(current_node, next_node, INF)
else:
next_in_node = get_in_node(ni, nj)
dinic.add_edge(current_node, next_in_node, INF)
else:
current_out_node = get_out_node(problem_row, current_j)
for di, dj in dirs:
ni = problem_row + di
nj = current_j + dj
if 1 <= ni <= H and 0 <= nj < W:
if ni == 1:
next_node = get_row1_node(nj)
dinic.add_edge(current_out_node, next_node, INF)
elif ni == H:
next_node = get_rowH_node(nj)
dinic.add_edge(current_out_node, next_node, INF)
else:
next_in_node = get_in_node(ni, nj)
dinic.add_edge(current_out_node, next_in_node, INF)
max_flow = dinic.max_flow(S, T)
if max_flow >= INF:
print(-1)
else:
print(max_flow)
if __name__ == '__main__':
main()