重み付き無向グラフで、すべての辺を通る閉路のうち最短経路の距離を求める。
https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_B
解説
グラフがオイラー閉路をもつ場合、すべての辺の重みの和が答えになる。そうでない場合、次数が奇数の頂点(奇点)が偶数個存在する。奇点同士でペアを作り、間に辺を追加することでオイラー閉路が作れる。実際には辺を追加するわけではなく最短経路をもう一度辿ることになる。奇点同士のマッチングを全探索し、最短経路の和の最小値を求め、すべての辺の重みの和を足したものが答えになる。
実装
長さが偶数のリストからマッチングを列挙するジェネレーターを使う。
def generate_matching(lst): n = len(lst) if n == 0: yield [] return x = lst[0] for i in range(1, n): y = lst[i] res = [z for z in lst if z != x and z != y] for matching in generate_matching(res): yield [(x, y)] + matching
例えば、$[0,1,2,3]$の場合は以下のように列挙できる。
for matching in generate_matching([0, 1, 2, 3]): print(matching) # [(0, 1), (2, 3)] # [(0, 2), (1, 3)] # [(0, 3), (1, 2)]
全点間の距離を求めるにはワーシャル・フロイド法を使う。
from collections import defaultdict INF = 1 << 30 n, m = map(int, input().split()) edge = [tuple(map(int, input().split())) for _ in range(m)] # 隣接リスト構築 graph = [defaultdict(lambda: INF) for _ in range(n)] for x, y, d in edge: graph[x][y] = min(graph[x][y], d) graph[y][x] = min(graph[y][x], d) # ワーシャルフロイド dist = [[INF] * n for _ in range(n)] for x in range(n): dist[x][x] = 0 for y in graph[x]: dist[x][y] = graph[x][y] for z in range(n): for x in range(n): for y in range(n): dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]) # 次数が奇数の点を列挙 deg = [0] * n for x, y, d in edge: deg[x] += 1 deg[y] += 1 odd_lst = [x for x in range(n) if deg[x] % 2] # 最小マッチング min_cost = INF for matching in generate_matching(odd_lst): min_cost = min(min_cost, sum(dist[x][y] for x, y in matching)) print(min_cost + sum(d for x, y, d in edge))
