SRM 693 div1 easy: BiconnectedDiv1

問題

TopCoder Statistics - Problem Statement

無向グラフが 2-edge-connected とは, 任意の頂点の組(u, v) について, グラフ上のどの辺 e を削除しても, いまだ u から v へのパスが存在することを言う。
n 頂点の無向グラフ G が与えられ, 以下の条件を満たす。

• i - i+1 がコスト w1[i] でつながっている。
• i - i+2 がコスト w2[i] でつながっている。

今, グラフ G が 2-edge-connected であるという条件を満たしたまま, 辺をいくつか削除し, 辺のコストの合計を最小にしたい。辺コストの合計の最小値を求めよ。

解法

まずググると, 2-edge-connected であるというのは, 「グラフに橋がない」というのと同値であることが分かります(まぁそうだろうとは思うでしょうが)。

頂点 0, N-1 の辺を取り除くと, 例えば 0 から出る辺が橋になってしまうので, この辺は取ってはいけないことがわかります。

で, 調べてみると辺の取り除き方としては, 頂点 1 から 頂点 n-2 まで, 頂点の index が上昇するように DAG を拾ってきたときの経路しか考えなくて良いことに気付きます。
実際,

• 辺の取り除き方を DAG 的にすると必ず 2-edge-connected になる
  • DAG 的であれば 1 <= i <= n-2 を満たす i について, 0 から i および i から n-1 へのパスがあります。なので, そこを経由すれば複数のパスがあります。
• 辺の取り除き方を DAG 的にしないと死ぬ
  • i -> i+1 と i -> i+2 の両方が取り除かれていた場合, i -> i+1 に行けません。i -> i+2 と i+1 -> i+2 が取り除かれていた場合も同様に i+1 -> i+2 に行けません。また, i -> i+2 と i+1 -> i+3 の両方が取り除かれていた場合, i+1 -> i+2 の辺が橋になっているので NG です。 DAG 的でないのは上記の 3 つのうちのいずれかが成り立っているはずなので死ぬことがわかりました。

なので, 単純に
dp[i] = (頂点 i までで取り除ける辺の最大コスト和)
とすれば良いです。

const int MAXN = 111;
int dp[MAXN];

class BiconnectedDiv1 {
public:
    int minimize(vector <int> w1, vector <int> w2) {
        int n = w1.size()+1;
        int sum = 0;
        for (int el : w1)
            sum += el;
        for (int el : w2)
            sum += el;
        for (int i = 2; i < n-1; i++) {
            dp[i] = dp[i-1]+w1[i-1];
            if (i > 2) dp[i] = max(dp[i], dp[i-2]+w2[i-2]);
        }
        return sum-dp[n-2];
    }
};