Day 138-Q3 | 割当問題のO(N³)解法

問題

$N\times N$ のコスト行列 $A$（$A_{ij}$：行 $i$ を列 $j$ に割り当てるコスト）が与えられる。各行を異なる列にちょうど1つずつ割り当てる完全マッチングの中で、コストの総和を最小にするものを求めよ（割当問題）。

行ごとに双対変数（ポテンシャル）$u_i,v_j$を保ちながら、未割当の列集合上で「縮約コスト $A_{ij}-u_i-v_j$」に基づく最短路的な探索（Dijkstra類似のラベリング）で1行ずつ増加路を見つける手法（Jonker-Volgenant法、しばしば「$O(N^3)$ Hungarian algorithm」と呼ばれる）を用いて、全体 $O(N^3)$ で解け。

入力形式

N
A_11 ... A_1N
...
A_N1 ... A_NN

制約

$1 \le N \le 500$

$0 \le A_{ij} \le 10^9$

出力: 1行目に最小コスト、2行目に各行(1-indexed)が割り当てられた列番号(1-indexed) N個

入出力例

入力例1

出力例1

5
2 1 3

入力例2

2
1 2
2 1

出力例2

2
1 2

概念図

ヒント（段階的開示）

ヒント1（方向性）

割当問題は二部グラフの最小重み完全マッチングであり、最大流的な発想（1行ずつ増加路を探して割り当てる）で解ける。ただし単純な増加路探索は重みを無視するので最小コストにならない。各行・列にポテンシャル$u_i,v_j$を持たせ、縮約コスト$A_{ij}-u_i-v_j\ge0$を保ちながら増加路を探すと、見つけた増加路が必ず最短になる。

ヒント2（アプローチ）

1行ずつ処理する。行$i$から未割当列に向けて、Dijkstra法のように未使用列の中で縮約コストが最小の列を確定させていく。確定列が既に他の行に割当済みならその行を玉突きで次のソースとして扱い、未割当列に到達したら増加路を逆にたどって割当を更新する。$p_j$: 列jの現在の割当行、$way_j$: 増加路復元用のポインタ。

ヒント3（誘導）

for i in range(1, n+1):
    p[0] = i
    j0 = 0
    minv = [INF]*(n+1)
    used = [False]*(n+1)
    while True:
        used[j0] = True
        i0 = p[j0]
        delta = INF; j1 = -1
        for j in range(1, n+1):
            if not used[j]:
                cur = a[i0][j] - u[i0] - v[j]
                if cur < minv[j]:
                    minv[j] = cur; way[j] = j0
                if minv[j] < delta:
                    delta = minv[j]; j1 = j
        for j in range(n+1):
            if used[j]:
                u[p[j]] += delta; v[j] -= delta
            else:
                minv[j] -= delta
        j0 = j1
        if p[j0] == 0:
            break
    while j0:
        j1 = way[j0]; p[j0] = p[j1]; j0 = j1

最終的な総コストは-v[0]、各列jの割当行はp[j]に格納される。

模範解答 (Python)

import sys


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

    a = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            a[i][j] = int(data[idx]); idx += 1

    INF = float('inf')
    u = [0] * (n + 1)
    v = [0] * (n + 1)
    p = [0] * (n + 1)
    way = [0] * (n + 1)

    for i in range(1, n + 1):
        p[0] = i
        j0 = 0
        minv = [INF] * (n + 1)
        used = [False] * (n + 1)
        while True:
            used[j0] = True
            i0 = p[j0]
            delta = INF
            j1 = -1
            for j in range(1, n + 1):
                if not used[j]:
                    cur = a[i0][j] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1 = j
            for j in range(n + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while j0:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1

    total = -v[0]
    col_of_row = [0] * (n + 1)
    for j in range(1, n + 1):
        col_of_row[p[j]] = j

    out = [str(total), ' '.join(str(col_of_row[i]) for i in range(1, n + 1))]
    print('\n'.join(out))


main()

Step-by-Step 解説

1縮約コストとポテンシャル
$A_{ij}-u_i-v_j\ge0$を保つように$u,v$を更新しながら探索すれば、負のコストが出現せず常に最短の増加路を貪欲に見つけられる（Dijkstraのポテンシャル法と同じ発想）。

2行を1つずつ確定
外側ループは行$i=1,\dots,N$を処理する。各行について未割当の列に到達するまでの最小コスト経路をDijkstra的に探索する。

3deltaによる一括更新
未確定列の中で最小の縮約コストdeltaを求め、確定済みのu,vをdelta分シフトし、未確定列のminvからdeltaを引く。Dijkstraの距離配列更新に相当する。

4増加路の反転
未割当列に到達したらway配列を逆にたどり割当pを更新する。二部マッチングの増加路反転と同じ操作。

5計算量
外側ループN回、各回の内側whileが最大N回、その中のforがO(N)で、1行あたりO(N²)、全体O(N³)。

よくあるミス

ミス	原因	正しい書き方
0-indexedと1-indexedを混同する	p[0]を番兵として使う設計を理解せず配列外参照やズレが起きる	行・列は1〜N、0番目は「未割当」を表す番兵として一貫して扱う
deltaの更新を確定済み要素にも適用する	usedの判定を誤り既に確定したu,vを二重更新する	used[j]がTrueならu[p[j]]+=delta,v[j]-=delta、Falseならminv[j]-=deltaのみ
総コストを再計算しようとして手間取る	ポテンシャルの性質を理解していない	-v[0]が直接最小コストの総和になることを利用する
wayの反転処理で無限ループする	j0が0になる条件を見落とす	while j0:でj0が0(番兵)になった時点で終了する
Nが大きいとPure PythonのO(N³)で実行時間が問題になる	定数倍を軽視する	NumPyのベクトル演算への置き換えや高速化を検討する（本問はアルゴリズム理解が主目的）

次のステップ

発展: 割当不可能な組を∞コストとして表現できるが、スパースな割当問題には最小費用流（Successive Shortest Path+ポテンシャル、Day104-Q5）の方が効率的な場合がある。両者の実装上の違いを比較せよ。
発展2: 縦横のサイズが異なる長方形コスト行列($N\ne M$)に一般化した割当問題を実装せよ。

自己評価

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

Day 138-Q3 — 割当問題の O(N³) 解法（Jonker-Volgenant型）

問題