結果

問題 No.3699 引き抜き交渉
コンテスト
ユーザー titia
提出日時 2026-11-01 04:59:13
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 92 ms / 2,000 ms
+ 307µs
コード長 3,577 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 99 ms
コンパイル使用メモリ 64,096 KB
実行使用メモリ 62,272 KB
最終ジャッジ日時 2026-11-01 04:59:17
合計ジャッジ時間 3,465 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N,M=list(map(int,input().split()))

# Dinic法高速化バージョン、
# https://atcoder.jp/contests/awc0071/submissions/80438454

from collections import deque

V=N+2
start=N
goal=N+1


# G[v] : 頂点 v から出る辺の番号一覧
# TO[e] : 辺 e の行き先
# CAP[e] : 辺 e の残余容量

# TO[G[u]],CAP[G[u]]により、行き先と容量を見る。
G=[[] for i in range(V)]
TO=[]
CAP=[]

SUM=0

for i in range(N):
    x,y=list(map(int,input().split()))

    if x==y:
        SUM+=x
        continue
    elif x>y:
        SUM+=x

        u,v,c=start,i,x-y
        e=len(TO)
        G[u].append(e)
        G[v].append(e^1)

        TO.append(v)
        TO.append(u)

        CAP.append(c)
        CAP.append(0)
    else:
        SUM+=y
        u,v,c=i,goal,y-x
        e=len(TO)
        G[u].append(e)
        G[v].append(e^1)

        TO.append(v)
        TO.append(u)

        CAP.append(c)
        CAP.append(0)

for i in range(M):
    x,y,z=list(map(int,input().split()))
    x-=1
    y-=1

    u,v,c=x,y,z
    e=len(TO)
    G[u].append(e)
    G[v].append(e^1)

    TO.append(v)
    TO.append(u)

    CAP.append(c)
    CAP.append(0)

    u,v,c=y,x,z
    e=len(TO)
    G[u].append(e)
    G[v].append(e^1)

    TO.append(v)
    TO.append(u)

    CAP.append(c)
    CAP.append(0)
    



ANS=0
while True:
    # まずBFSでレベルグラフを作る

    DIS=[-1]*V
    Q=deque([start])
    DIS[start]=0

    while Q:
        x=Q.popleft()

        # ゴールまでの距離が確定していたら、
        # それと同じ距離以上の頂点は探索しない
        if DIS[goal] != -1 and DIS[x] >= DIS[goal]:
            break
        for e in G[x]:
            if CAP[e]==0:
                continue

            to=TO[e]
            
            if DIS[to]==-1:
                DIS[to]=DIS[x]+1

                Q.append(to)

    if DIS[goal]==-1:
        break

    # it[v] : 頂点 v で次に調べる辺の位置
    it = [0] * V

    # レベルグラフ上でDFS。
    # goalからstartに向かって探索する

    MINCOST=[1<<30]*V
    ROUTE=[-1]*V
    
    while True:
        STACK=[goal]
        found=False

        while STACK:
            NOW=STACK[-1]

            if NOW==start:
                # 増加路が見つかった
                cost=MINCOST[start]
                ANS+=cost

                # goalからstartに戻りながら容量を更新
                i=goal

                while i!=start:
                    e=ROUTE[i]
                    j=TO[e^1]

                    # 飽和する辺なら、この辺の探索位置を進める
                    if CAP[e]==cost:
                        it[i]+=1

                    CAP[e]-=cost
                    CAP[e^1]+=cost

                    i=j

                found=True
                break

            # NOWに入ってくる辺を逆向きに調べる
            while it[NOW]<len(G[NOW]):
                r=G[NOW][it[NOW]]

                e=r^1
                prev=TO[r]

                if CAP[e]>0 and DIS[prev]+1==DIS[NOW]:
                    break

                it[NOW]+=1

            if it[NOW]<len(G[NOW]):
                r=G[NOW][it[NOW]]
                e=r^1
                prev=TO[r]

                ROUTE[NOW]=e
                MINCOST[prev]=min(MINCOST[NOW],CAP[e])

                STACK.append(prev)

            else:
                STACK.pop()

                if STACK:
                    it[STACK[-1]]+=1

        if not found:
            break
            

print(SUM-ANS)
0