#1174954 (PyPy3) No.3668 Minimum Cut

• 問題: No.3668 Minimum Cut
• ユーザー: 👑 みうね
• 提出日時: 2026-08-04 13:31:11
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 1,231 ms / 2,000 ms
• コード長: 5,540 bytes
• コンパイル時間: 242 ms
• コンパイル使用メモリ: 95,816 KB
• 実行使用メモリ: 89,856 KB
• 最終ジャッジ日時: 2026-09-04 22:00:59
• 合計ジャッジ時間: 10,307 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 39

ソースコード

import sys

def solve():
    # 1. 入力の一括読み込み（超高速化）
    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])
    
    # 2. 多重辺を統合して辺の総数 E を減らす（キラーケース対策）
    edge_dict = {}
    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 (u, v) in edge_dict:
            edge_dict[(u, v)] += c
        else:
            edge_dict[(u, v)] = c
            
    num_unique_edges = len(edge_dict)
    
    # 3. オブジェクト生成を避け、すべて1次元配列でグラフを管理（C言語と同等の速度にする）
    head = [-1] * (N + 1)
    to_list = [0] * (2 * num_unique_edges)
    cap_list = [0] * (2 * num_unique_edges)
    nxt_list = [-1] * (2 * num_unique_edges)
    rev_list = [0] * (2 * num_unique_edges)
    
    max_cap = 0
    edge_cnt = 0
    
    for (u, v), c in edge_dict.items():
        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)
    path = [-1] * (N + 1)
    
    flow = 0
    INF = 10**18
    
    # 容量スケーリングの初期しきい値(最大容量以下の最大の2のべき乗)
    delta = 1
    while delta <= max_cap:
        delta *= 2
    delta //= 2
    
    # 4. メインループ
    while delta > 0:
        while True:
            # --- BFSパート ---
            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:
                    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]
            
            # SからTへたどり着けなくなったら今の delta を終了
            if level[T] < 0:
                break
            
            for i in range(1, N + 1):
                iter_edge[i] = head[i]
            
            # --- 非再帰（反復処理）DFSパート ---
            path_sz = 0
            v = S
            while True:
                e = iter_edge[v]
                advanced = False
                # 次に進める辺を探す
                while e != -1:
                    nxt = to_list[e]
                    if cap_list[e] >= delta and level[v] < level[nxt]:
                        path[path_sz] = e
                        path_sz += 1
                        iter_edge[v] = e # 状態を保存
                        v = nxt
                        advanced = True
                        break
                    e = nxt_list[e]
                    iter_edge[v] = e # 無効な辺をスキップ
                    
                # 進めなかった場合（行き止まり）
                if not advanced:
                    if path_sz == 0:
                        break # 完全に探索し尽くしたら終了
                    # 1つ前の頂点に戻る
                    path_sz -= 1
                    e = path[path_sz]
                    v = to_list[rev_list[e]] # 親ノードを取得
                    # 行き止まりになった辺はもう使わないようにする
                    iter_edge[v] = nxt_list[iter_edge[v]]
                else:
                    # ゴール(T)にたどり着いた場合
                    if v == T:
                        push_f = INF
                        for i in range(path_sz):
                            pe = path[i]
                            if cap_list[pe] < push_f:
                                push_f = cap_list[pe]
                        
                        flow += push_f
                        
                        # 経路の容量を更新し、ボトルネック（容量がdelta未満になった最初の辺）を探す
                        bottleneck_idx = -1
                        for i in range(path_sz):
                            pe = path[i]
                            cap_list[pe] -= push_f
                            cap_list[rev_list[pe]] += push_f
                            if cap_list[pe] < delta and bottleneck_idx == -1:
                                bottleneck_idx = i
                                
                        # ボトルネックになった位置まで経路を巻き戻す
                        e = path[bottleneck_idx]
                        v = to_list[rev_list[e]]
                        path_sz = bottleneck_idx

        # しきい値を半分にして再開
        delta //= 2
        
    print(flow)

if __name__ == '__main__':
    solve()