結果
問題 |
No.2713 Just Solitaire
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:30:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 3,079 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,976 KB |
実行使用メモリ | 78,532 KB |
最終ジャッジ日時 | 2025-03-20 20:31:17 |
合計ジャッジ時間 | 2,901 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
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() if v == t: break 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) return level[t] != -1 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]: pushed = self.dfs_flow(edge.to, t, min(flow, edge.capacity), level, ptr) if pushed > 0: edge.capacity -= pushed self.graph[edge.to][edge.rev].capacity += pushed return pushed ptr[v] += 1 return 0 def max_flow(self, s, t): flow = 0 level = [-1] * self.size while self.bfs_level(s, t, level): ptr = [0] * self.size while True: pushed = self.dfs_flow(s, t, float('inf'), level, ptr) if pushed == 0: break flow += pushed level = [-1] * self.size return flow def main(): import sys input = sys.stdin.read().split() idx = 0 N, M = int(input[idx]), int(input[idx+1]) idx +=2 A = list(map(int, input[idx:idx+N])) idx +=N B = list(map(int, input[idx:idx+M])) idx +=M # Read bonuses bonuses = [] for _ in range(M): K_i = int(input[idx]) C_i = list(map(int, input[idx+1: idx+1+K_i])) idx += K_i +1 bonuses.append(C_i) total_B = sum(B) # Build the graph # Nodes: # source:0 # bonuses: 1..M # cards: M+1 ... M+N (for card 1..N) # sink: M+N+1 num_nodes = M + N + 2 dinic = Dinic(num_nodes) sink = M + N +1 INF = 1 << 60 for i in range(M): dinic.add_edge(0, i+1, B[i]) for j in range(N): card_node = M+1 +j dinic.add_edge(card_node, sink, A[j]) for i in range(M): bonus_node = i +1 for c in bonuses[i]: card = c -1 # 0-based card_node = M+1 + card dinic.add_edge(bonus_node, card_node, INF) max_flow = dinic.max_flow(0, sink) print(total_B - max_flow) if __name__ == "__main__": main()