Day 148-Q1 | MPM法（Malhotra-Pramodh-Kumar Algorithm）

問題

$N$頂点$M$辺のDAG（レベルグラフ、すべての辺は$u<v$）が与えられる。頂点$0$が始点$s$、頂点$N-1$が終点$t$。以下のMPM法の手続きを実行し、総流量と reference vertex の選択順序を求めよ。

各頂点$v$のポテンシャル $\mathrm{pot}(v)$: $s$は出容量の総和、$t$は入容量の総和、それ以外は $\min(\text{入容量総和},\text{出容量総和})$。
行き止まり除去: $s,t$以外で入または出容量が0の頂点を連鎖的に除去する。
生存頂点のうちポテンシャル最小（同点なら添字最小）の頂点$u$を選ぶ。
$\mathrm{pot}(u)=0$なら除去して手順3へ。そうでなければ$f=\mathrm{pot}(u)$を$u\to t$へ前方プッシュ、$s\to u$へ後方プルし、$u$を除去、$f$を総流量に加算。
$s$または$t$が消えるまで繰り返す。

入力形式

N M
u_1 v_1 c_1
:
u_M v_M c_M

制約

$2 \le N \le 8$

$N-1 \le M \le 12$

$1 \le c_i \le 10$

各辺は $u_i < v_i$、同一$(u,v)$は高々1回

入出力例

入力例1

出力例1

8
2 3 0

入力例2

出力例2

7
2 1

入力例2では頂点2（ポテンシャル3）→頂点1（ポテンシャル4）の順に飽和し、合計$3+4=7$が総流量と一致する。

概念図：頂点ポテンシャルによる逐次飽和（入力例2）

ヒント（段階的開示）

ヒント1（方向性）

Dinic法の「current-arcによる辺ベースDFS」との違いを意識する。MPM法は毎回「今どの頂点が一番"細い"か」を全体から探し、その頂点を中心に流量を押し切る。

ヒント2（アプローチ）

ポテンシャルは「その頂点を通過できる流量の上限」。$u$を選んで$f=\mathrm{pot}(u)$だけ流すとき、前方向・後方向は独立に貪欲DFSで処理してよい（$f\le$出次容量の総和なので必ず流しきれる）。

ヒント3（誘導）

def push(node, amount, t, outn, cap):
    if node == t:
        return
    rem = amount
    for w in list(outn[node]):
        if rem == 0:
            break
        c = cap.get((node, w), 0)
        if c <= 0:
            continue
        use = min(rem, c)
        cap[(node, w)] = c - use
        rem -= use
        push(w, use, t, outn, cap)

模範解答 (Python)

import sys

def solve(N, edges, s, t):
    cap = {}
    outn = [[] for _ in range(N)]
    inn = [[] for _ in range(N)]
    for (u, v, c) in edges:
        cap[(u, v)] = cap.get((u, v), 0) + c
    for (u, v) in list(cap.keys()):
        outn[u].append(v)
        inn[v].append(u)

    alive = [True] * N

    def out_cap(u):
        return sum(cap.get((u, v), 0) for v in outn[u] if alive[v])

    def in_cap(v):
        return sum(cap.get((u, v), 0) for u in inn[v] if alive[u])

    def potential(v):
        if v == s:
            return out_cap(v)
        if v == t:
            return in_cap(v)
        return min(in_cap(v), out_cap(v))

    total = 0
    order = []

    while alive[s] and alive[t]:
        changed = True
        while changed:
            changed = False
            for v in range(N):
                if alive[v] and v != s and v != t:
                    if out_cap(v) == 0 or in_cap(v) == 0:
                        alive[v] = False
                        changed = True
            if not (alive[s] and alive[t]):
                break
        if not (alive[s] and alive[t]):
            break

        cands = [v for v in range(N) if alive[v]]
        pots = {v: potential(v) for v in cands}
        if all(p == 0 for p in pots.values()):
            break
        u = min(cands, key=lambda v: (pots[v], v))
        f = pots[u]
        if f == 0:
            alive[u] = False
            continue
        order.append(u)
        total += f

        def push(node, amount):
            if node == t:
                return
            rem = amount
            for w in list(outn[node]):
                if rem == 0:
                    break
                if not alive[w] and w != t:
                    continue
                c = cap.get((node, w), 0)
                if c <= 0:
                    continue
                use = min(rem, c)
                cap[(node, w)] = c - use
                rem -= use
                push(w, use)
        push(u, f)

        def pull(node, amount):
            if node == s:
                return
            rem = amount
            for w in list(inn[node]):
                if rem == 0:
                    break
                if not alive[w] and w != s:
                    continue
                c = cap.get((w, node), 0)
                if c <= 0:
                    continue
                use = min(rem, c)
                cap[(w, node)] = c - use
                rem -= use
                pull(w, use)
        pull(u, f)

        alive[u] = False

    return total, order


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx + 1]); idx += 2
    edges = []
    for _ in range(M):
        u, v, c = int(data[idx]), int(data[idx + 1]), int(data[idx + 2]); idx += 3
        edges.append((u, v, c))
    total, order = solve(N, edges, 0, N - 1)
    print(total)
    print(' '.join(map(str, order)))


main()

Step-by-Step 解説

1ポテンシャルの意味
頂点$v$のポテンシャルは「$v$を経由して流せる量の上界」。入る容量の総和、出る容量の総和の小さい方で決まる。$s$は出るだけ、$t$は入るだけなので特別扱いする。

2最小ポテンシャル頂点から確定
ポテンシャル最小の$u$を選ぶと、$u$を通る流量は必ず$\mathrm{pot}(u)$に固定してよい。$u$がボトルネックなので、それ以上流そうとしても流せない。

3前方プッシュ・後方プルの独立性
$f=\mathrm{pot}(u)$を$u\to t$、$s\to u$それぞれ独立に流しきれることはポテンシャルの定義から保証される。経路選択は貪欲でよい。

4行き止まり除去との相互作用
頂点を1つ除去するたび新たな行き止まりが生まれうる。変化がなくなるまで連鎖的に除去しないとポテンシャル計算が不正確になる。

よくあるミス

ミス	原因	正しい書き方
最小ポテンシャル頂点を値のみで選ぶ	同点時の扱いを決めておらず出力順序が不定	`min(cands, key=lambda v: (pots[v], v))`で添字を第2キーにする
$u$除去前に容量を先にゼロクリア	push/pullが辿るべき残余容量を失う	先にpush/pullで容量を減算してから`alive=False`にする
行き止まり除去を1回しか回さない	連鎖的な行き止まり発生を見落とす	`changed`フラグで変化がなくなるまでループする
$s,t$にも一般頂点と同じ式を適用	$s$に入辺、$t$に出辺が存在しないケースを考慮していない	$s$は出容量のみ、$t$は入容量のみでポテンシャルを定義する
総流量に別の量を加算してしまう	「除去した頂点のポテンシャルの合計＝ブロッキングフロー量」を誤解	reference vertex選択のたびに`total += f`を正しく加算する

次のステップ

発展: 本問は単一フェーズのみ。実際のMPM法は毎回BFSでレベルグラフを再構築し、レベルが無くなるまで繰り返して真の最大流を$O(V^3)$で求める。
次回予告: Main-Lorentz法（簡略版・文字列中の全周期的極大区間を数え上げる）

自己評価

完全理解おおむね理解要復習

Day 148-Q1 — MPM法（Malhotra-Pramodh-Kumar Algorithm・頂点ポテンシャルによるブロッキングフロー構成）

問題