Day 089-Q3 — Karp's Minimum Mean Cycle（最小平均閉路検出）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $i$ は $u_i \to v_i$ で重み $w_i$（負の値もあり得る整数）を持つ。グラフ中の閉路のうち「閉路の重みの合計 ÷ 閉路の辺数」（平均重み）を最小化する閉路を求め、その最小平均値を既約分数 $p/q$（$q>0$）の形式で出力せよ。グラフには少なくとも1つの閉路が存在することが保証される。

入出力例

3 4
1 2 1
2 1 -4
2 3 1
3 1 1

-3/2

3 3
1 2 2
2 3 2
3 1 3

7/3

例1: 2頂点閉路 $1\to2\to1$ の平均 $(1-4)/2=-3/2$ が最小。例2: 唯一の閉路 $1\to2\to3\to1$ の平均 $7/3$。

概念図: 仮想始点 $d_0(v)=0$ から $k$ 辺ウォークDPで閉路を検出

ヒント

d = [[INF]*(n+1) for _ in range(n+1)]
for v in range(1, n+1):
    d[0][v] = 0
for k in range(1, n+1):
    for u in range(1, n+1):
        if d[k-1][u] == INF: continue
        for v, w in adj[u]:
            d[k][v] = min(d[k][v], d[k-1][u] + w)
# 最終判定は Fraction(d[n][v]-d[k][v], n-k) の max/min

模範解答

import sys
from fractions import Fraction

def main():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        adj[u].append((v, w))

    INF = float('inf')
    d = [[INF] * (n + 1) for _ in range(n + 1)]
    for v in range(1, n + 1):
        d[0][v] = 0
    for k in range(1, n + 1):
        for u in range(1, n + 1):
            if d[k - 1][u] == INF:
                continue
            for v, w in adj[u]:
                if d[k - 1][u] + w < d[k][v]:
                    d[k][v] = d[k - 1][u] + w

    best = None
    for v in range(1, n + 1):
        if d[n][v] == INF:
            continue
        worst = None
        for k in range(n):
            if d[k][v] == INF:
                continue
            val = Fraction(d[n][v] - d[k][v], n - k)
            if worst is None or val > worst:
                worst = val
        if worst is not None and (best is None or worst < best):
            best = worst

    print(f"{best.numerator}/{best.denominator}")

main()

計算量: DPテーブルの計算が $O(NM)$、最終集計が $O(N^2)$。全体で $O(NM)$。

Step-by-Step 解説

Step 1: 「全頂点から無料でスタート」する仮想始点DP

$d_0(v)=0$（全頂点）とすることで、グラフが強連結でなくてもどこかにある最小平均閉路を正しく検出できる。

Step 2: ちょうど $k$ 辺のウォークの最短値を計算

$d_k(v)=\min_{(u,v)\in E} d_{k-1}(u)+w(u,v)$ の緩和を $N$ 回繰り返す。$O(NM)$。

Step 3: Karp の公式を適用

Step 4: 厳密な分数比較

浮動小数点誤差を避けるため fractions.Fraction で厳密に計算する。

よくあるミス

次のステップ

• 発展問題: 最小平均閉路を実際に1つ復元する
• 発展問題: 二分探索 + 負閉路検出（Bellman-Ford）版との比較

自己評価