概要

すべての辺を少なくとも1回通って始点に戻る最短巡回路（中国人郵便配達人問題）を、奇数次数の頂点が高々16個という制約を利用して、ビットマスクDPによる最小重み完全マッチングで解く問題です。

考察

オイラー回路との関係

すべての辺をちょうど1回ずつ通って始点に戻る巡回路をオイラー回路といいます。オイラー回路が存在する条件は「グラフが連結で、すべての頂点の次数が偶数」です。

もしグラフがこの条件を満たしていれば、答えは全辺の重みの合計 \(\sum W_i\) です。余分な辺を通る必要がありません。

奇数次数の頂点がある場合

次数が奇数の頂点があるとオイラー回路は存在しません。このとき、いくつかの辺を2回以上通る（追加コストを払う）ことで、すべての頂点の次数を偶数にしてオイラー回路が作れるようにする必要があります。

グラフ理論の基本的な性質として、奇数次数の頂点の個数は必ず偶数個です。奇数次数の頂点をペアにして、各ペアの最短経路上の辺を追加で通ることで、そのペアの両端の次数の偶奇を反転させることができます。

最小コストにするには

奇数次数の頂点たちを完全マッチング（すべてをペアに分ける）して、各ペア間の最短距離の合計が最小になるようにすればよいです。これが追加で通る分のコストの最小値となります。

なぜビットマスクDPが使えるか

奇数次数の頂点数が16以下という制約があるため、\(2^{16} = 65536\) 状態のビットマスクDPで最小重み完全マッチングを効率的に求められます。素朴に全ペアリングを列挙すると \((15)!! = 2027025\) 通りとなりますが、ビットマスクDPなら重複計算を省けます。

アルゴリズム

1. グラフを読み込み、全辺の重みの合計 \(S = \sum W_i\) と各頂点の次数を計算する。

2. 奇数次数の頂点を列挙する。もし0個ならオイラー回路が存在するので \(S\) を出力して終了。

3. 奇数次数の頂点間の最短距離を求める。各奇数次数頂点を始点としてDijkstra法を実行し、他の奇数次数頂点への最短距離を記録する（最大16回のDijkstra）。

4. ビットマスクDPで最小重み完全マッチングを求める。

   • \(dp[\text{mask}]\) = \(\text{mask}\) で表される頂点集合をすべてペアにしたときの最小コスト
   • \(dp[0] = 0\) から始め、各状態で最も番号の小さい未マッチ頂点を選び、残りの未マッチ頂点とペアにする遷移を行う。
   • 「最も番号の小さい未マッチ頂点を固定する」ことで、同じペアリングを重複して数えることを防ぐ。

5. 答え = \(S + dp[\text{full\_mask}]\)（全辺の重み合計 + 最小マッチングコスト）

計算量

• 時間計算量: \(O(K \cdot (N + M) \log N + 2^K \cdot K)\)
  • \(K\) は奇数次数の頂点数（\(K \leq 16\)）
  • Dijkstra法を \(K\) 回実行: \(O(K \cdot (N + M) \log N)\)
  • ビットマスクDP: \(O(2^K \cdot K)\)
• 空間計算量: \(O(N + M + 2^K)\)

実装のポイント

• Dijkstraの始点は奇数次数頂点のみで十分です。最大16回なので十分高速です。

• ビットマスクDPで「最小番号の未マッチ頂点を固定」するテクニックにより、各ペアリングをちょうど1回だけ考慮でき、状態数が \(O(2^K)\) に抑えられます。

• 多重辺がありますが、Dijkstra法の隣接リストに普通に追加するだけで正しく動作します。最短経路計算では自動的に最短の辺が選ばれます。

• float('inf') の代わりに十分大きい整数を使うと高速化できますが、本解法では \(K \leq 16\) のため問題なく間に合います。

  ソースコード

import heapq
import sys
from itertools import combinations

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    # Build adjacency list for Dijkstra
    adj = [[] for _ in range(N + 1)]
    total_weight = 0
    degree = [0] * (N + 1)
    
    for i in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        w = int(input_data[idx]); idx += 1
        adj[u].append((v, w))
        adj[v].append((u, w))
        degree[u] += 1
        degree[v] += 1
        total_weight += w
    
    # Find odd-degree vertices
    odd_vertices = [v for v in range(1, N + 1) if degree[v] % 2 == 1]
    num_odd = len(odd_vertices)
    
    # If no odd vertices, the graph is Eulerian, answer is sum of all weights
    if num_odd == 0:
        print(total_weight)
        return
    
    # Compute shortest paths between all odd-degree vertices using Dijkstra
    # num_odd <= 16
    odd_set = set(odd_vertices)
    odd_index = {v: i for i, v in enumerate(odd_vertices)}
    
    # dist[i][j] = shortest path between odd_vertices[i] and odd_vertices[j]
    dist_matrix = [[0] * num_odd for _ in range(num_odd)]
    
    for i, src in enumerate(odd_vertices):
        # Dijkstra from src
        dist = [float('inf')] * (N + 1)
        dist[src] = 0
        pq = [(0, src)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in adj[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        
        for j, target in enumerate(odd_vertices):
            dist_matrix[i][j] = dist[target]
    
    # Minimum weight perfect matching on odd vertices using bitmask DP
    # dp[mask] = minimum cost to match all vertices in mask
    full_mask = (1 << num_odd) - 1
    dp = [float('inf')] * (1 << num_odd)
    dp[0] = 0
    
    for mask in range(full_mask + 1):
        if dp[mask] == float('inf'):
            continue
        # Find the lowest unset bit (first unmatched vertex)
        first = -1
        for b in range(num_odd):
            if not (mask & (1 << b)):
                first = b
                break
        if first == -1:
            continue
        # Try pairing first with every other unmatched vertex
        for second in range(first + 1, num_odd):
            if not (mask & (1 << second)):
                new_mask = mask | (1 << first) | (1 << second)
                cost = dp[mask] + dist_matrix[first][second]
                if cost < dp[new_mask]:
                    dp[new_mask] = cost
    
    # Answer is total weight of all edges + minimum matching cost
    print(total_weight + dp[full_mask])

if __name__ == '__main__':
    main()

---

この解説は claude4.6opus-thinking によって生成されました。