結果
問題 | No.904 サメトロ |
ユーザー | None |
提出日時 | 2021-04-01 22:27:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 1,000 ms |
コード長 | 5,249 bytes |
コンパイル時間 | 591 ms |
コンパイル使用メモリ | 87,284 KB |
実行使用メモリ | 78,076 KB |
最終ジャッジ日時 | 2023-08-23 06:22:02 |
合計ジャッジ時間 | 5,385 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,544 KB |
testcase_01 | AC | 75 ms
71,284 KB |
testcase_02 | AC | 78 ms
75,796 KB |
testcase_03 | AC | 88 ms
76,384 KB |
testcase_04 | AC | 86 ms
75,940 KB |
testcase_05 | AC | 72 ms
71,536 KB |
testcase_06 | AC | 82 ms
75,652 KB |
testcase_07 | AC | 91 ms
75,816 KB |
testcase_08 | AC | 111 ms
77,656 KB |
testcase_09 | AC | 71 ms
71,388 KB |
testcase_10 | AC | 98 ms
76,528 KB |
testcase_11 | AC | 109 ms
77,220 KB |
testcase_12 | AC | 80 ms
75,428 KB |
testcase_13 | AC | 73 ms
71,276 KB |
testcase_14 | AC | 89 ms
76,388 KB |
testcase_15 | AC | 84 ms
75,836 KB |
testcase_16 | AC | 114 ms
78,076 KB |
testcase_17 | AC | 75 ms
71,340 KB |
testcase_18 | AC | 75 ms
71,428 KB |
testcase_19 | AC | 81 ms
75,780 KB |
testcase_20 | AC | 77 ms
71,336 KB |
testcase_21 | AC | 98 ms
76,736 KB |
testcase_22 | AC | 88 ms
76,164 KB |
testcase_23 | AC | 93 ms
76,328 KB |
testcase_24 | AC | 77 ms
71,540 KB |
testcase_25 | AC | 74 ms
71,300 KB |
testcase_26 | AC | 117 ms
77,916 KB |
testcase_27 | AC | 85 ms
76,560 KB |
testcase_28 | AC | 74 ms
71,684 KB |
testcase_29 | AC | 83 ms
76,572 KB |
testcase_30 | AC | 76 ms
71,540 KB |
testcase_31 | AC | 75 ms
71,424 KB |
testcase_32 | AC | 72 ms
71,164 KB |
testcase_33 | AC | 74 ms
71,164 KB |
testcase_34 | AC | 74 ms
71,480 KB |
testcase_35 | AC | 74 ms
71,336 KB |
ソースコード
class MaxFlow: def __init__(self, n=0): self._n = n self.g = [[] for _ in range(n)] self.pos = [] def add_edge(self, frm, to, cap): m = len(self.pos) e1 = MaxFlow._edge(to, cap) e2 = MaxFlow._edge(frm, 0) e1.rev = e2 e2.rev = e1 self.pos.append(e1) self.g[frm].append(e1) self.g[to].append(e2) return m class edge: def __init__(self, frm, to, cap, flow): self.frm = frm self.to = to self.cap = cap self.flow = flow def __iter__(self): yield self.frm yield self.to yield self.cap yield self.flow def get_edge(self, i): """ i 番目に追加された辺について (from, to, 初期の cap, 現在の流量(始めは 0)) """ e1 = self.pos[i] e2 = e1.rev return MaxFlow.edge(e2.to, e1.to, e1.cap + e2.cap, e2.cap) def edges(self): """ get_edge の返り値をリストで並べたもの """ return [self.get_edge(i) for i in range(len(self.pos))] def change_edge(self, i, new_cap, new_flow): e = self.pos[i] e.cap = new_cap - new_flow e.rev.cap = new_flow def flow(self, s, t, flow_limit=0XFFFFFFFFFFFFFFF): g = self.g flow = 0 while flow < flow_limit: level = [-1] * self._n level[s] = 0 que = [None] * self._n ql = 0 qr = 1 que[0] = s unreached = True while unreached and ql < qr: v = que[ql] ql += 1 for e in g[v]: to = e.to if e.cap and level[to] < 0: level[to] = level[v] + 1 if to == t: unreached = False break que[qr] = to qr += 1 if unreached: return flow ptr = [len(es) for es in g] stack = [] v = t up = flow_limit - flow res = 0 while True: if v == s or not ptr[v]: if v == s: res = up while stack: tmp = res e, up, res = stack.pop() e.cap -= tmp e.rev.cap += tmp res += tmp if res < up: v = e.to break else: flow += res break i = ptr[v] while i: i -= 1 e = g[v][i] if level[e.to] == level[v] - 1 and e.rev.cap: ptr[v] = i stack.append((e.rev, up, res)) v = e.to up = min(up, e.rev.cap) res = 0 break else: ptr[v] = i return flow def min_cut(self, s): """ 残余グラフから到達可能な頂点集合を返す。 流量の最大値を十分大きくとった場合、この頂点集合はmin_cutとなる。 """ visited = [False] * self._n que = [None] * self._n ql = 0 qr = 1 que[0] = s visited[s] = True while ql < qr: p = que[ql] ql += 1 for e in self.g[p]: if e.cap and not visited[e.to]: visited[e.to] = True que[qr] = e.to qr += 1 return visited def draw(self): """ :return: グラフを可視化 """ import matplotlib.pyplot as plt import networkx as nx G = nx.DiGraph() for frm, to, cap, cap_now in self.edges(): G.add_edge(frm, to, label="{}/{}".format(cap_now,cap)) edge_labels = {(i, j): w['label'] for i, j, w in G.edges(data=True)} pos = nx.spring_layout(G) nx.draw_networkx(G, pos, with_labels=True, connectionstyle='arc3, rad = 0.1') nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) plt.axis("off") plt.show() class _edge: def __init__(self, to, cap): self.to = to self.cap = cap def __iter__(self): yield self.to yield self.cap def example(): global input example = iter( """ 7 6 0 1 4 1 3 1 1 4 1 2 5 1 3 6 1 4 6 1 """ .strip().split("\n")) input = lambda: next(example) ##################################################################################### import sys input = sys.stdin.readline # example() N=int(input()) mf = MaxFlow(2*N) for i in range(1,N): a,b=map(int, input().split()) for j in range(1,N): if i==j:continue mf.add_edge(i,N+j,a) mf.add_edge(0,i,a) mf.add_edge(N+i,N,b) f=mf.flow(0,N) print(f+1)