中国配達人問題

Chinese Postman Problem | Aizu Online Judge

• 元のグラフにいくつかパスを加えてオイラー閉路にする。
• あらかじめダイクストラ法最小パスを求めておいて、dp を使ってそれらのうち最適なものを計算する。

//
// オイラー路とは、グラフ（グラフ理論）の全ての辺を1度だけ通る路のこと。
// 全ての辺を1度だけ通る閉路は、オイラー閉路という。
// グラフGの辺をすべて通るようなオイラー閉路を持つグラフのことをオイラーグラフという。
// またGの辺をすべて通るような、閉路でないオイラー路を持つグラフのことを準オイラーグラフ
// という。
//
// オイラーグラフと準オイラーグラフは、一筆書き可能である。
// 連結グラフ G に対して次が成り立つ。
//
//  * Gがオイラーグラフ ⇔ Gの全ての頂点の次数が偶数
//  * Gが準オイラーグラフ ⇔ Gの頂点のうち、次数が奇数であるものがちょうど2つ
//
class chinise_postman_problem {
public:
    void solve(void) {
        int V, E;
        cin>>V>>E;
        vector<vector<pair<int,int>>> tree(V);
        REP(i, E)
        {
            int s, t, d;
            cin>>s>>t>>d;
            tree[s].emplace_back(t,d);
            tree[t].emplace_back(s,d);
        }

        // 全辺のコスト
        // 少なくとも一度は全ての辺を移動するのでそれにかかるコスト
        ll  total = 0;
        //
        // オイラー閉路がある場合はそれで終了。
        // 出て行く辺の数が奇数の頂点(奇数点)を巡る最小コストを加えればよい。
        //
        vector<int> odds;
        REP(v, V)
        {
            for (const auto &e : tree[v])
                total += e.second;
            // 奇点を集める
            if (tree[v].size() % 2 == 1)
                odds.push_back(v);
        }
        // 無効グラフなので重複分割る
        total /= 2;

        int n = odds.size();
        const int inf = (1<<30);

        // 奇数点から別の奇数点へ移動するときのコスト
        vector<vector<int>> weight(n,vector<int>(n,inf));

        // 出て行く辺が奇数の頂点を巡回
        // O(V*E*log(V))
        REP(u, n)
        {
            int s = odds[u];
            vector<int> dist(V, inf);

            dist[s] = 0;
            priority_queue<pair<int,int>> que;

            // dijkstra
            que.emplace(s, 0);
            while (!que.empty())
            {
                int v, d;
                tie(v, d) = que.top();
                que.pop();
                if ( dist[v] < d )
                    continue;

                for (const auto &e : tree[v])
                {
                    int to, cost;
                    tie(to, cost) = e;
                    if ( dist[v] + cost < dist[to] )
                    {
                        dist[to] = dist[v] + cost;
                        que.emplace(to, dist[to]);
                    }
                }
            }
            REP(v, n)
                weight[u][v] = dist[odds[v]];
        }
        int N = (1<<n);
        // グラフにいくつか辺(パス)を追加してオイラー閉路を完成させる
        // どのパスを追加するのかに dp を使って最小値を計算する
        vector<int> best(N, inf);
        best[0] = 0;

        // O(2^V*V^2)
        for (int S = 0; S < N; ++S)
        {
            for (int v = 0; v < n; ++v)
            {
                if ( (S & (1<<v)) )
                    continue;
                for (int u = v+1; u < n; ++u)
                {
                    if ( (S & (1<<u)) )
                        continue;
                    best[S|(1<<v)|(1<<u)] = min(best[S|(1<<v)|(1<<u)], best[S]+weight[u][v]);
                }
            }
        }
        cout<<total+best[N-1]<<endl;
    }
};