結果

問題 No.904 サメトロ
ユーザー NoneNone
提出日時 2021-04-02 23:23:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,768 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 111,944 KB
最終ジャッジ日時 2024-06-06 08:25:02
合計ジャッジ時間 7,957 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 192 ms
80,212 KB
testcase_01 WA -
testcase_02 AC 235 ms
81,656 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 44 ms
57,208 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 45 ms
57,156 KB
testcase_19 WA -
testcase_20 AC 146 ms
79,376 KB
testcase_21 WA -
testcase_22 AC 276 ms
91,484 KB
testcase_23 WA -
testcase_24 AC 156 ms
79,044 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 401 ms
111,944 KB
testcase_28 AC 40 ms
54,824 KB
testcase_29 AC 51 ms
65,152 KB
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 44 ms
56,468 KB
testcase_33 AC 44 ms
56,068 KB
testcase_34 AC 44 ms
58,244 KB
testcase_35 AC 71 ms
74,908 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

##############################################################

import sys
input = sys.stdin.readline




# example()

INF=10**2

N=int(input())

mf = MaxFlow(2*N+2)

SA,SB=0,0
for i in range(1,N):
    a,b=map(int, input().split())
    for j in range(N):
        if i==j:continue
        mf.add_edge(i,N+j,a)
    mf.add_edge(2*N,i,a)
    mf.add_edge(N+i,2*N+1,b)
    SA+=a
    SB+=b

for i in range(N):
    mf.add_edge(0,N+i,INF)

mf.add_edge(N,2*N+1,INF)

from copy import deepcopy

def test(x):
    mf2=deepcopy(mf)
    mf2.add_edge(2*N,0,x)
    mf2.flow(2*N,2*N+1)
    flg=1
    for i in range(2*N):
        if i==0 or i==N: continue
        frm,to,cap,now=mf.get_edge(i)
        if now!=0:
            flg=0
    return flg

a=binary_search_int(SB,-1,test)

print(SB-a+1)
0