結果
問題 |
No.957 植林
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:58:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,287 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,348 KB |
実行使用メモリ | 195,144 KB |
最終ジャッジ日時 | 2025-06-12 13:59:03 |
合計ジャッジ時間 | 19,024 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 TLE * 1 -- * 29 |
ソースコード
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 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 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, float('inf'), level, ptr) if f == 0: break flow += f level = [-1] * self.size def main(): import sys input = sys.stdin.read data = input().split() idx = 0 H = int(data[idx]) idx += 1 W = int(data[idx]) idx += 1 G = [] for _ in range(H): row = list(map(int, data[idx:idx+W])) G.append(row) idx += W R = list(map(int, data[idx:idx+H])) idx += H C = list(map(int, data[idx:idx+W])) idx += W total_r = sum(R) total_c = sum(C) total = total_r + total_c S = 0 T = 1 node_r_start = 2 node_c_start = node_r_start + H node_m_start = node_c_start + W total_nodes = node_m_start + H * W dinic = Dinic(total_nodes) for i in range(H): r_node = node_r_start + i dinic.add_edge(S, r_node, R[i]) for j in range(W): c_node = node_c_start + j dinic.add_edge(S, c_node, C[j]) for i in range(H): for j in range(W): m_node = node_m_start + i * W + j g = G[i][j] r_node = node_r_start + i c_node = node_c_start + j dinic.add_edge(r_node, m_node, g) dinic.add_edge(c_node, m_node, g) dinic.add_edge(m_node, T, g) max_flow = dinic.max_flow(S, T) print(total - max_flow) if __name__ == "__main__": main()