Day 105-Q5 | Karp's Minimum Mean Cycle（最小平均閉路）

問題

$N$頂点$M$辺の有向グラフが与えられる。各辺は重み$w_i$（負も可）を持つ。グラフ中の閉路（頂点や辺の再訪を許す一般の閉路）のうち、平均重み（辺重み合計÷辺数）が最小のものを求めよ。閉路が存在しなければ$-1$。

Karp's Algorithm（1978）は$O(VE)$でこれを厳密に解く。仮想始点$s$から各頂点への「ちょうど$k$本の辺を使った最短ウォーク長」$d_k(v)$を$k=0,\dots,N$について計算し、

$$\mu^{*} = \min_{v} \max_{0 \le k \le N-1} \frac{d_N(v) - d_k(v)}{N-k}$$

で最小平均閉路の値が求まる。$N$本の辺を使えば鳩の巣原理でどこかの頂点を再訪する＝閉路を含むことを利用している。

入力形式

N M
u_1 v_1 w_1
...
u_M v_M w_M

制約

$1 \le N \le 300$

$0 \le M \le 2000$

$-10^6 \le w_i \le 10^6$

グラフは連結とは限らない

入出力例

入力例1

出力例1

1.00000000

三角形$1\to2\to3\to1$の平均重みは$(1+1+1)/3=1$。2-閉路$1\to4\to1$は$(10+10)/2=10$。最小は$1$。

入力例2

3 2
1 2 5
2 3 3

出力例2

-1

閉路を持たないDAGなので$-1$。

概念図: dk(v)の階段とKarpの判定式

ヒント（段階的開示）

ヒント1: 方向性

平均$\mu$以下の閉路の有無を判定する問題に帰着し$\mu$を二分探索する方法（辺重みから$\mu$を引いてベルマン-フォードで負閉路検出）もあるが、二分探索を使わず1回の$O(VE)$のDPだけで厳密な最小平均値を直接計算する方法がある。始点$s$から「ちょうど$k$本の辺」を使ったウォークの最短長を$k=0$から$N$まで順に計算していくとどうなるか考えよう。

ヒント2: アプローチ

すべての頂点に到達できる仮想始点$s$を用意する（コスト0の辺で$s$から全頂点へ直結）。$d_k(v)$（$s$から$v$へちょうど$k$本の辺のウォーク、再訪可）を$k=0..N$についてDPで計算する。Karpの定理により最小平均閉路は$\mu^{*}=\min_v \max_{0\le k

ヒント3: 誘導（コード骨格）

d = [[INF] * V for _ in range(V + 1)]  # V = N+1(仮想始点込み)
d[0][s] = 0
for k in range(1, V + 1):
    for (u, v, w) in all_edges:
        if d[k-1][u] < INF:
            d[k][v] = min(d[k][v], d[k-1][u] + w)

best = None
for v in range(V):
    if d[V][v] == INF: continue
    worst = max((d[V][v]-d[k][v])/(V-k)
                for k in range(V) if d[k][v] < INF)
    if best is None or worst < best:
        best = worst
# best is None -> 閉路なし(-1)

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    edges = []
    for _ in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        w = int(data[idx]); idx += 1
        edges.append((u, v, w))

    V = n + 1
    s = n
    all_edges = list(edges) + [(s, v, 0) for v in range(n)]

    INF = float('inf')
    d = [[INF] * V for _ in range(V + 1)]
    d[0][s] = 0

    for k in range(1, V + 1):
        dk_prev = d[k - 1]
        dk = d[k]
        for (u, v, w) in all_edges:
            if dk_prev[u] < INF:
                nd = dk_prev[u] + w
                if nd < dk[v]:
                    dk[v] = nd

    best = None
    for v in range(V):
        if d[V][v] == INF:
            continue
        worst = None
        for k in range(V):
            if d[k][v] == INF:
                continue
            ratio = (d[V][v] - d[k][v]) / (V - k)
            if worst is None or ratio > worst:
                worst = ratio
        if worst is not None:
            if best is None or worst < best:
                best = worst

    if best is None:
        print(-1)
    else:
        print(f"{best:.8f}")


solve()

計算量: $O(V \cdot E)$（$V=N+1$、$E=M+N$）。ランダム300ケースで単純閉路の全列挙による厳密解との一致を確認済み。

Step-by-Step 解説

1仮想始点の導入
コスト0の辺で$s$から全頂点へ直結し、Karpの定理の前提（sから全頂点に到達可能）を満たす。閉路の平均重みには影響しない。

2d_k(v)の計算
$d_0(s)=0$から、各$k$について全辺を1回ずつ緩和して$d_k$を求める。頂点の再訪を許すウォークである点が最短路と異なる。

3Karpの判定式
$d_V(v)$が有限な頂点について$(d_V(v)-d_k(v))/(V-k)$の最大値を計算する。これは「vに至るまでに通過した閉路のうち平均重みが最大のもの」を抽出する。

4閉路なしの判定
すべての$v$で$d_V(v)$が$\infty$なら、$V$本の辺を使うウォークが存在しない＝閉路なし。$-1$を出力する。

よくあるミス

ミス	原因	正しい書き方
仮想始点を導入せず元の頂点1つを$s$に固定	$s$から到達できない部分に最小平均閉路がある場合を見逃す	コスト0の辺で全頂点に直結する仮想始点を追加する
$d_k(v)$を単純パスの最短距離と誤解しダイクストラで計算	負辺を含む再訪可能ウォークはダイクストラで正しく計算できない	全辺を$k$回ずつ緩和する素朴なDP($O(VE)$)を使う
内側maxで$d_k(v)=\infty$の$k$を除外し忘れる	$\infty$を含む比較で誤った最大値になる	`if d[k][v]==INF: continue`で明示的にスキップする
`best`の初期値をNoneにせず0やINFにする	「閉路が見つからない」と「平均重み0の閉路が見つかった」を区別できない	`best=None`で初期化し、閉路なしなら$-1$を出力する

次のステップ

発展: 最小平均閉路の実際の頂点列を復元する（argmaxを与える$k$を記録しトレースする）
発展: 二分探索+ベルマン-フォード法による負閉路検出との計算量・実装量のトレードオフを比較する
次回予告: Suurballe's Algorithm の頂点素バージョン（頂点分割テクニックとの融合）

自己評価

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

Day 105-Q5 — Karp's Minimum Mean Cycle（最小平均閉路）

問題