99全國賽 洗街車路線問題

題目：

給一張圖，有 N 個點(<=1500)， M 條邊(<=N(N-1)/2)，與起點 S，邊上有權重

求出由 S 出發至少經過每條邊一次再回到 S，所需的最小花費。

(題目保證奇點 <= 14)



解法：

這題也想了兩三天，算是一步一步想出來的，

首先，由於要最小花費，故若每條邊都走過一次會是最佳的情況，

於是可以聯想到 Euler Circuit 問題，

只要圖上的每一點都是偶點，必定可以形成 Euler Circuit。

於是，問題轉化成，

如何在這張圖上加邊，使得此圖沒有奇點，並且所有邊的總和最小。

我們從奇點開始著手，

對於兩奇點 A、B，要將兩點都變成偶點，且不影響原圖，

就是把 A、B 路徑上的邊都加一條，

又可以發現，當此路徑是最短路徑時，花費的增加也最少，

於是我們將所有奇點當作原點做最短路，

問題便轉化成一般圖最小權最大匹配，

由於點的數量最多只有14個，情況總數為

C(14,2)*C(12,2)*...C(2,2) / 7! = 135135，

故可以使用枚舉來輕鬆解決。

AC (4ms, 390KB)