ARC 078: F - Mole and Abandoned Mine

問題概要

arc078.contest.atcoder.jp

頂点数  N ,辺の数  M の無向グラフ  G が与えられるので,頂点 1 から頂点  N へのパスが一通りになるように辺を取り除く.

ただし,辺を取り除くにはコストがかかるため,取り除いた辺のコストの総和が最小となるようにする.

解法

辺を取り除くのではなく,辺が無い状態から頂点 1 から頂点  N へのパスが一通りになるように辺を追加し,辺を追加するコストは取り除くコストと同じだとして追加した辺のコストの総和を最大化することを考える.

最大化した解を  x とすると,元の問題の解は  (全ての辺のコストの総和) - x で求まる.

 x はdpで求めることができる.

次のようなグラフを考える (辺のコストは記していない).

f:id:t-tatsukawa:20170717051835p:plain:w500

解が以下のようなグラフになったとする.青色で囲まれているところをターミナルと呼ぶことにする.

このターミナルに含まれる辺は橋(取り除くと連結では無くなるような辺)となる.

緑色で囲まれている頂点集合は,各ターミナルに接続されている連結成分を指す. この連結成分はあるターミナルとは互いに素で,ターミナルと一辺で接続されている. なので,連結成分の頂点同士の辺は全て追加すると良い(最終的に最大化に持っていくため).

この連結成分の頂点同士の辺を全て追加した時のコストは前処理で計算できる.

f:id:t-tatsukawa:20170717045355p:plain:w500

dpの式は以下のようになる.

 dp[S][t] := Sに含まれる頂点を用いており,ターミナル tを見ているときのコストの最大値

更新は以下のように考えれば良い.

ターミナル  i を見ている時,隣接していて  S に含まれてない頂点集合の中から次のターミナル候補  j S の補集合の各部分集合に対して更新式を立てることができるのでそれを計算すれば良い.

f:id:t-tatsukawa:20170717051832p:plain:w500

ソースコード

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int MAX = 16;

int dp[1 << MAX][MAX];
int costs[1 << MAX];
int G[MAX][MAX];

int main() {
    int N, M, a, b, c, all_costs = 0;

    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        a--, b--;
        G[a][b] = G[b][a] = c;
        all_costs += c;
    }

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            for(int k = j+1; k < N; k++) {
                if(!((i >> j) & 1)) continue;
                if(!((i >> k) & 1)) continue;
                costs[i] += G[j][k];
            }
        }
    }

    for(int i = 0; i < (1 << N); i++) {
        for(int j = 0; j < N; j++) {
            dp[i][j] = -INF;
        }
    }

    for(int i = 0; i < (1 << N); i++) {
        // set to terminal 0
        if(i & 1) {
            dp[i][0] = costs[i];
        }
    }

    int mask = ((1 << N) - 1);

    for(int S = 0; S < (1 << N); S++) {
        for(int i = 0; i < N; i++) {
            // select terminal i in S
            if(dp[S][i] == -INF) continue;
            // create a sets "sup" that is sub S
            int sup = (~S) & mask;
            int sub = sup;

            for(int sub = sup; sub; sub = ((sub-1) & sup)) {
                // select terminal j in "sub"
                for(int j = 0; j < N; j++) {
                    if(!((sub >> j) & 1)) continue;
                    if(G[i][j] == 0) continue;

                    dp[S|sub][j] = max(dp[S|sub][j], dp[S][i] + G[i][j] + costs[sub]);
                }
            }
        }
    }

    cout << all_costs - dp[(1<<N)-1][N-1] << endl;
}

所感

解説通りの解法だと思うのでアレ. 厳密な証明とか計算量の計算とかできてないので見直してみる.