Day 114-Q2 | 最小コスト時間比閉路

問題

$N$ 頂点 $M$ 辺の有向グラフがある。各辺 $i$ は始点 $u_i$、終点 $v_i$、コスト $c_i$、所要時間 $t_i > 0$ を持つ。

グラフ中の任意の閉路 $C$ について、その コスト時間比 を $$ R(C) = \frac{\sum_{e \in C} c_e}{\sum_{e \in C} t_e} $$ と定義する。閉路が少なくとも1つ存在するとき、$R(C)$ を最小化する閉路の値 $R^*$ を求めよ。存在しない場合は -1 を出力せよ。

入力形式

N M
u_1 v_1 c_1 t_1
u_2 v_2 c_2 t_2
...
u_M v_M c_M t_M

制約

$2 \le N \le 300$

$1 \le M \le 3000$

$1 \le u_i, v_i \le N$

$-10^4 \le c_i \le 10^4$

$1 \le t_i \le 10^4$

誤差 $10^{-6}$ 以内で正解

入出力例

入力例1

出力例1

2.000000

閉路 $1\to2\to3\to1$ のコスト合計 $12$、時間合計 $6$ で比は $2.0$。他に閉路がないのでこれが最小。

入力例2

2 2
1 2 5 1
2 1 -1 1

出力例2

2.000000

概念図: 比の最小化を「判定問題」に変換する二分探索

ヒント（段階的開示）

ヒント1: 方向性

「比の最小化」を直接扱うのは難しいが、値 $\lambda$ を固定して「$R(C) < \lambda$ となる閉路が存在するか？」という 判定問題 に変換すると扱いやすくなる。この判定は $\lambda$ について単調なので、答えを二分探索できる。

ヒント2: アプローチ

$R(C) < \lambda \iff \sum c_e < \lambda \sum t_e \iff \sum (c_e - \lambda t_e) < 0$ である。各辺の重みを $w_e(\lambda) = c_e - \lambda t_e$ と定義したグラフに 負閉路が存在するかどうか を判定すればよい。負閉路検出は全頂点を距離0で初期化するBellman-Ford法を使う。負閉路があれば $\lambda$ を小さく、なければ $\lambda$ を大きくして二分探索を進める。

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

def has_negative_cycle(lam):
    dist = [0.0] * (N + 1)  # 全頂点を仮想始点として同時初期化
    for it in range(N):
        updated = False
        for u, v, c, t in edges:
            w = c - lam * t
            if dist[u] + w < dist[v] - 1e-9:
                dist[v] = dist[u] + w
                updated = True
                if it == N - 1:
                    return True
        if not updated:
            return False
    return False

lo, hi = -1e4, 1e4
for _ in range(100):
    mid = (lo + hi) / 2
    if has_negative_cycle(mid):
        hi = mid
    else:
        lo = mid
print(hi)

模範解答 (Python)

import sys

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, t = int(data[idx]), int(data[idx+1]), int(data[idx+2]), int(data[idx+3])
        idx += 4
        edges.append((u, v, c, t))

    def has_negative_cycle(lam):
        dist = [0.0] * (N + 1)  # 全頂点を仮想始点扱いで0初期化
        for it in range(N):
            updated = False
            for u, v, c, t in edges:
                w = c - lam * t
                nd = dist[u] + w
                if nd < dist[v] - 1e-9:
                    dist[v] = nd
                    updated = True
                    if it == N - 1:
                        return True
            if not updated:
                return False
        return False

    if M == 0:
        print(-1)
        return

    # 閉路の存在判定はDFSで行う（二分探索だけでは「閉路が1つもない」ケースを判定できない）
    adj = [[] for _ in range(N + 1)]
    for u, v, c, t in edges:
        adj[u].append(v)
    color = [0] * (N + 1)
    has_cycle = [False]
    sys.setrecursionlimit(5000)

    def dfs(u):
        if has_cycle[0]:
            return
        color[u] = 1
        for v in adj[u]:
            if color[v] == 1:
                has_cycle[0] = True
                return
            if color[v] == 0:
                dfs(v)
                if has_cycle[0]:
                    return
        color[u] = 2

    for s in range(1, N + 1):
        if color[s] == 0:
            dfs(s)
        if has_cycle[0]:
            break

    if not has_cycle[0]:
        print(-1)
        return

    lo, hi = -1e4 - 1.0, 1e4 + 1.0
    for _ in range(100):
        mid = (lo + hi) / 2
        if has_negative_cycle(mid):
            hi = mid
        else:
            lo = mid

    print(f"{hi:.6f}")

main()

計算量: 判定1回が Bellman-Ford で $O(NM)$、二分探索を100回繰り返して $O(100 \cdot NM)$。$N=300, M=3000$ で約 $9\times10^7$ 回の演算。全頂点を距離0で初期化することで、単一始点からの到達可能性を気にせず全体の負閉路を検出できる。

Step-by-Step 解説

1「比の最小化」を「判定問題」に変換する
$R^*$を直接求める代わりに、「$\lambda$以下の比を持つ閉路が存在するか」を判定する関数を作り、$\lambda$について二分探索する。分数計画法の標準的な手筋。

2判定条件を線形の重み付け問題に変形する
$t_e>0$なので$\sum c_e < \lambda \sum t_e \iff \sum(c_e-\lambda t_e)<0$。よって辺重み$c_e-\lambda t_e$の閉路和が負になる閉路が存在するかという負閉路検出問題に帰着する。

3負閉路検出はBellman-Fordを全頂点0初期化で行う
全頂点の距離を0で初期化すると、コスト0の辺で全頂点に接続された仮想始点から始めたのと同じになり、グラフ内のどこにある負閉路も検出できる。

4二分探索の範囲と収束条件
$R(C)$の取りうる範囲は$[-10^4,10^4]$。100回程度繰り返せば要求精度$10^{-6}$を十分満たす。

5閉路の存在自体を先に確認する
閉路が1つもない場合、二分探索は誤った値を返すため、事前にDFSで有向閉路の存在を判定し、なければ-1を出力する。

よくあるミス

ミス	原因	正しい書き方
Bellman-Fordを単一始点から始めてしまう	通常の最短路と同じ書き方を流用する	全頂点を距離0で初期化し、仮想始点からの緩和とみなす
閉路が存在しない場合に二分探索の結果をそのまま出力してしまう	「判定関数が常にFalseを返す」ケースを想定していない	事前にDFSで閉路の存在を確認し、なければ`-1`を出力する
浮動小数点比較を`<`だけで行い誤差で誤判定する	イプシロンを考慮しない	`dist[u]+w < dist[v]-eps`のように許容誤差を入れる
二分探索の初期範囲を見積もらずコストの値そのままにしてしまう	$\lambda$の理論上の範囲を計算していない	コスト・時間の最大絶対値から$R(C)$の範囲を見積もり余裕を持たせる

次のステップ

発展: 負閉路自体（辺のリスト）を復元し、比が最小になる具体的な閉路を出力する
発展: Karp's Minimum Mean Cycle（Day100 Q5、$t_e=1$固定の特殊ケース）とアルゴリズムの違いを比較する
発展: 辺容量制約を追加し、最小比が実現可能なフローの下での最適比に変わる場合を考える

自己評価

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

Day 114-Q2 — 最小コスト時間比閉路（Minimum Cost-to-Time Ratio Cycle・二分探索+Bellman-Ford負閉路判定）

問題