Day 101-Q1 — 中国郵便配達問題（Chinese Postman Problem）

2026-07-24 赤色 Master / Phase 8+ ★★★★★★★★★ 最小重み完全マッチング + 全点対最短路

問題

無向連結グラフが与えられる。すべての辺を少なくとも1回ずつ通り、出発点に戻ってくる閉路の最小コストを求めよ。「中国郵便配達問題（Route Inspection Problem）」として知られる古典的な組合せ最適化問題である。

全頂点の次数が偶数ならオイラー閉路が存在し、答えは全辺の重み総和になる。奇数次数の頂点が存在する場合、それらをうまくペアにして各ペア間の最短路をもう一度余分に通行する必要がある。奇数次数頂点は必ず偶数個存在する（握手補題）ので、それらを完全マッチングでペアにし、ペアの最短路長の総和が最小になるマッチングを選べばよい。

入力形式

N M
u_1 v_1 w_1
:
u_M v_M w_M

制約

$2 \le N \le 12$
$N-1 \le M \le N(N-1)/2$
$1 \le w_i \le 1000$
単純・連結グラフ、1-indexed

入出力例

入力例1

4 5
1 2 1
2 3 1
3 4 1
4 1 1
1 3 5

出力例1

11

四角形（各辺重み1）+対角線1-3（重み5）。奇数次数頂点は1,3。全辺総和=9。1-3の最短路は直通5でなく迂回2の方が短い。答え=9+2=11。

入力例2

3 3
1 2 1
2 3 1
1 3 1

出力例2

3

三角形は全頂点偶数次数（次数2）。そのままオイラー閉路が存在し、追加の重複通行は不要。答え=全辺総和の3。

概念図

奇数次数頂点をペアにして最短路を追加通行 1 2 3 4 1 1 1 1 対角5 緑破線=最短路(2経由 or 4経由): コスト2で1-3を再訪 奇数次数={1,3}（●）→ 最小重みペアリング(bitDP) → 全辺総和9 + マッチングコスト2 = 11

ヒント（段階的開示）

ヒント1: 方向性
「奇数次数の頂点が2個以下ならその2点間の最短路を1回余分に歩けばよい」という直感はすぐ思いつくが、奇数次数頂点が4個、6個…と増えた場合、どの2頂点同士をペアにするかで余分な移動距離の総和が変わってくる。全ペアの組み合わせを列挙して比較する必要がある。
ヒント2: アプローチ
まず全点対間の最短路長を前計算する（$N\le12$なのでFloyd-Warshallで$O(N^3)$）。次に、次数が奇数の頂点集合（個数$K$は必ず偶数、$K\le N\le12$）に対して、「$K$頂点を過不足なくペアにする完全マッチングのうち、ペア間最短路長の総和が最小のもの」をビットDPで求める。$K\le12$なら$O(2^K K)$のbitDPで解ける。答えは「全辺の重み総和」+「そのマッチングコスト」。
ヒント3: 誘導（コード骨格） 
dp = [INF] * (1 << K)
dp[0] = 0
for mask in range(1 << K):
    if dp[mask] == INF:
        continue
    i = 0
    while (mask >> i) & 1:
        i += 1
    if i >= K:
        continue
    for j in range(i + 1, K):
        if not (mask >> j) & 1:
            nmask = mask | (1 << i) | (1 << j)
            cost = dp[mask] + dist[odds[i]][odds[j]]
            dp[nmask] = min(dp[nmask], cost)
# 答え = 全辺総和 + dp[(1<

「一番小さい未使用のインデックス $i$ を必ず誰かとペアにする」制約で同じペア集合の重複計算を防ぐ。

模範解答 (Python)

import sys


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

    INF = float('inf')
    dist = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        dist[i][i] = 0

    total = 0
    deg = [0] * (N + 1)

    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        total += w
        deg[u] += 1
        deg[v] += 1
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    for k in range(1, N + 1):
        dk = dist[k]
        for i in range(1, N + 1):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            for j in range(1, N + 1):
                nd = dik + dk[j]
                if nd < di[j]:
                    di[j] = nd

    odds = [v for v in range(1, N + 1) if deg[v] % 2 == 1]
    K = len(odds)
    full = 1 << K
    dp = [INF] * full
    dp[0] = 0

    for mask in range(full):
        if dp[mask] == INF:
            continue
        i = 0
        while (mask >> i) & 1:
            i += 1
        if i >= K:
            continue
        for j in range(i + 1, K):
            if not (mask >> j) & 1:
                nmask = mask | (1 << i) | (1 << j)
                cost = dp[mask] + dist[odds[i]][odds[j]]
                if cost < dp[nmask]:
                    dp[nmask] = cost

    print(total + dp[full - 1])


solve()
計算量: $O(N^3 + 2^K K)$（$N\le12$, $K\le N$なので余裕）。

Step-by-Step 解説

1入力読み込みと基礎統計
辺の重み総和`total`と各頂点の次数`deg`を同時に集計し、距離行列を初期化。
2全点対最短路（Floyd-Warshall）
$O(N^3)$で中継点を1つずつ試し距離を更新。
3奇数次数頂点の抽出
握手補題より個数$K$は必ず偶数。
4最小重み完全マッチング（bitDP）
未マッチの最小インデックス頂点を必ずペアにすることで重複計算を回避。
5出力
「全辺総和 + 最小マッチングコスト」が答え。

よくあるミス

ミス原因正しい書き方
奇数次数頂点を貪欲にペアにする局所最適が全体最適にならないケースを見逃すbitDPで全ペア組み合わせを厳密に評価する
マッチングコストに直接辺の重みを使う迂回路の方が短い場合を見落とす必ずFloyd-Warshallの最短路長を使う
bitDPで同じペア集合を2回数える「未マッチの最小インデックス固定」制約を入れ忘れる`i`をmaskの最小の未セットビットに固定する
$K=0$のケースでエラー`dp[full-1]`=`dp[0]`と気づかず特殊分岐を書く特殊分岐不要、コードのまま動く

次のステップ

  • 発展: 有向グラフ版の中国郵便配達問題（入次数≠出次数の頂点があれば最小費用流で不足分を補う、MCMFで解ける）
  • 発展: 一部の辺だけ通行必須とするRural Postman Problem（NP困難）との違いを調べる
  • 次回予告: Karger-Stein法（乱択最小カットの分割統治高速化）

自己評価

自分の回答

気づき・メモ