中國郵遞員問題(參考poj 2404)

題目敘述：

有一張連通圖，找出經過所有的邊且回到原處的最小權重和

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

經過所有的邊且要回到原處，很顯然就是一個歐拉回路

但是跟歐拉回路不一樣的地方在於他沒有限制每個邊只能走一次

也就是說，只要是一張連通圖，就一定會有解

但其實你可以把它想成是歐拉回路的進階版本

歐拉迴路中，絕對不能有奇度的點（因為進出的數量相同）

只要有奇度的點，想要回到啟始點，就必定會重複

用重複的概念，可以把原本是奇度的點，修改成全部都是偶度的

至於要怎麼修呢？你可以想成我們對這張圖增加一些邊

原本偶度的點要增加偶數條，奇度的點要增加奇數條

換一種方式想，其實就是要在奇度點之間兩兩建立一條路徑，並使權重和最小

因為奇度點一定是偶數的（整張圖的度數必定是偶數），假設為2N

那就要建立N條路徑，使得這些奇度點兩兩配對，也就是所謂的一般配對

普通的題目N應該很小，所以可以直接用狀態壓縮DP（如本題）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

算法描述：

1. 建出兩兩奇度點之間的距離（用Floyd或點太多用Dijkstra）

2. 將奇度點兩兩配對，並使權重和最小

3. 新增的邊權＋原本圖上的邊權和 ＝ 答案

//By momo
#include<cstdio>
#include<vector>
#include<algorithm>

#define N 17
#define INF 999999999
#define SZ(x) (int)((x).size())

using namespace std;

int n, dis[N][N], deg[N], dp[1<<N];
vector<int> odd;

void floyd()
{
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++) if(dis[i][k] != INF)
            for(int j = 0; j < n; j++) if(dis[k][j] != INF)
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
}

int dfs(int cb)
{
    if(cb == 0) return 0;
    if(dp[cb] != INF) return dp[cb];

    for(int i = 0; i < n; i++)
    {
        if(!(cb & (1<<i))) continue;
        for(int j = 0; j < n; j++)
        {
            if(i == j || !(cb & (1<<j))) continue;
            int v = dfs(cb^(1<<i)^(1<<j));
            dp[cb] = min(dp[cb], v+dis[odd[i]][odd[j]]);
        }
    }
    return dp[cb];
}

int main()
{
    while(scanf("%d", &n), n != 0)
    {
        int ans = 0, m;
        fill(deg, deg+n, 0);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dis[i][j] = INF;

        scanf("%d", &m);
        for(int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c); a--, b--;
            dis[a][b] = dis[b][a] = min(c, dis[a][b]);
            deg[a]++, deg[b]++, ans += c;
        }
       
        floyd();
       
        odd.clear();
        for(int i = 0; i < n; i++)
            if(deg[i]&1) odd.push_back(i);
        n = SZ(odd);

        for(int i = 0; i < (1<<n); i++) dp[i] = INF;
        printf("%d\n", ans + dfs((1<<n)-1));
    }
}