結果

問題 No.3668 Minimum Cut
コンテスト
ユーザー 👑 みうね
提出日時 2026-08-04 13:28:41
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 3,536 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 263 ms
コンパイル使用メモリ 95,544 KB
実行使用メモリ 232,192 KB
最終ジャッジ日時 2026-09-04 22:00:50
合計ジャッジ時間 11,708 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 TLE * 2 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

# 再帰上限の引き上げ（頂点数N=2000なら深さ2000までいく可能性があるため）
sys.setrecursionlimit(100000)

def solve():
    # 入力を一括読み込み（超高速化）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    N = int(input_data[0])
    M = int(input_data[1])
    S = int(input_data[2])
    T = int(input_data[3])
    
    # Pythonでのオブジェクト生成ペナルティを避けるため、1次元配列でグラフを管理
    head = [-1] * (N + 1)
    
    # 辺のデータ（2*M本分の固定長配列をあらかじめ確保）
    to_list = [0] * (2 * M)
    cap_list = [0] * (2 * M)
    nxt_list = [-1] * (2 * M)
    rev_list = [0] * (2 * M)
    
    max_cap = 0
    edge_cnt = 0
    
    idx = 4
    for _ in range(M):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        c = int(input_data[idx+2])
        idx += 3
        
        if c > max_cap: 
            max_cap = c
            
        # 順方向の辺
        e1 = edge_cnt
        to_list[e1] = v
        cap_list[e1] = c
        nxt_list[e1] = head[u]
        rev_list[e1] = e1 + 1
        head[u] = e1
        
        # 逆方向の辺（残余グラフ用）
        e2 = e1 + 1
        to_list[e2] = u
        cap_list[e2] = 0
        nxt_list[e2] = head[v]
        rev_list[e2] = e1
        head[v] = e2
        
        edge_cnt += 2

    # BFS用・DFS用の配列もあらかじめ確保
    level = [-1] * (N + 1)
    queue = [0] * (N + 1)
    iter_edge = [-1] * (N + 1)
    
    def bfs(s, t, delta):
        # 配列の初期化（リスト内包表記より速い）
        for i in range(1, N + 1):
            level[i] = -1
        level[s] = 0
        
        qh = 0
        qt = 0
        queue[qt] = s
        qt += 1
        
        while qh < qt:
            v = queue[qh]
            qh += 1
            
            e = head[v]
            while e != -1:
                # 容量が delta 以上の辺だけを使う
                if cap_list[e] >= delta:
                    nxt = to_list[e]
                    if level[nxt] < 0:
                        level[nxt] = level[v] + 1
                        queue[qt] = nxt
                        qt += 1
                e = nxt_list[e]
        return level[t] >= 0

    def dfs(v, t, f, delta):
        if v == t: return f
        
        e = iter_edge[v]
        while e != -1:
            nxt = to_list[e]
            if cap_list[e] >= delta and level[v] < level[nxt]:
                push_f = f if f < cap_list[e] else cap_list[e]
                d = dfs(nxt, t, push_f, delta)
                if d > 0:
                    cap_list[e] -= d
                    cap_list[rev_list[e]] += d
                    iter_edge[v] = e
                    return d
            e = nxt_list[e]
            
        iter_edge[v] = -1
        return 0

    flow = 0
    INF = 10**18
    
    # 最初のしきい値(delta)を最大容量を超えない2のべき乗に設定
    delta = 1
    while delta <= max_cap:
        delta *= 2
    delta //= 2

    # スケーリング付きDinic法の実行
    while delta > 0:
        while bfs(S, T, delta):
            for i in range(1, N + 1):
                iter_edge[i] = head[i]
            
            while True:
                f = dfs(S, T, INF, delta)
                if f == 0:
                    break
                flow += f
        delta //= 2
        
    print(flow)

if __name__ == '__main__':
    solve()
0