Day 058-Q3 — 最大重み閉路分解

問題

$N$ 頂点の完全有向グラフが与えられる。各辺 $(i, j)$（$i \ne j$）に重み $w_{ij}$ が付く。

閉路分解とは、各頂点をちょうど 1 つの閉路に属するよう辺を選んで閉路の集合に分解すること。
閉路分解の「重み」= 選んだすべての辺の重みの和として、最大重みの閉路分解の重みを出力せよ。

入出力例

3
0 3 1
2 0 4
3 1 0

10

閉路 $1 \to 2 \to 3 \to 1$: 重み $3 + 4 + 3 = 10$。
閉路 $1 \to 3 \to 2 \to 1$: 重み $1 + 1 + 2 = 4$。最大は 10。

概念図: 閉路分解 = 二部マッチング

ヒント（段階的開示）

import numpy as np
from scipy.optimize import linear_sum_assignment

# 最大化 → 符号反転して最小化
W = np.array(W_input, dtype=float)
for i in range(N):
    W[i][i] = -10**9  # 自己ループ禁止

row_ind, col_ind = linear_sum_assignment(-W)
ans = int(round(W[row_ind, col_ind].sum()))
print(ans)

模範解答 (Python)

コピーimport sys
from scipy.optimize import linear_sum_assignment
import numpy as np
input = sys.stdin.readline

def main():
    N = int(input())
    W = []
    for i in range(N):
        row = list(map(int, input().split()))
        W.append(row)

    W = np.array(W, dtype=float)

    # 自己ループを禁止
    for i in range(N):
        W[i][i] = -10**9

    # 最大重み完全二部マッチング（linear_sum_assignment は最小化）
    row_ind, col_ind = linear_sum_assignment(-W)

    ans = int(round(W[row_ind, col_ind].sum()))
    print(ans)

main()

# --- scipy が使えない場合の Hungarian Algorithm O(N^3) ---
def hungarian(cost, N):
    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
        minVal = [INF] * (N + 1)
        used = [False] * (N + 1)
        while True:
            used[j0] = True
            i0, delta, j1 = p[j0], INF, -1
            for j in range(1, N + 1):
                if not used[j]:
                    cur = cost[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minVal[j]:
                        minVal[j] = cur
                        way[j] = j0
                    if minVal[j] < delta:
                        delta = minVal[j]
                        j1 = j
            for j in range(N + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minVal[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while j0:
            p[j0] = p[way[j0]]
            j0 = way[j0]
    return sum(cost[i][p[i+1]-1] for i in range(N))

Step-by-Step 解説

Step 1: 閉路分解 = 順列

$N$ 頂点の有向グラフで各頂点の入次数 = 出次数 = 1 の辺集合は、閉路分解と等価。これは順列 $\sigma: V \to V$（各頂点 $i$ は $\sigma(i)$ に移動）に対応する。

Step 2: 順列 = 二部マッチング

左頂点 $\{1,\ldots,N\}$（出発）× 右頂点 $\{1,\ldots,N\}$（到着）の二部グラフで完全マッチング = 順列。辺 $(i_L, j_R)$ の重みは $w_{ij}$。

Step 3: Hungarian Algorithm

重み行列に対して $O(N^3)$ で最大重み完全二部マッチングを解く。$N=500$ で $1.25 \times 10^8$ 演算 → Python では scipy 推奨。

Step 4: 自己ループ禁止

対角成分に $-10^9$（十分小さな値）を設定して自己ループを使わないようにする。

よくあるミス

次のステップ

発展問題: 閉路分解において「各閉路の長さが $\ge 3$」という制約を追加した場合の最大重みを求めよ（最小長制約付き閉路分解）。

自己評価