https://beta.atcoder.jp/contests/arc078/submissions/2417009

問題概要

N頂点M辺の単純連結無向グラフが与えられる。このグラフから任意の辺集合を取り除いて頂点1から頂点Nまでの単純パスがただ1通りに定まるようにするとき、取り除く辺のコストの和の最小値を求めよ。

N <= 15

M <= N(N-1)/2

解法

取り除く辺のコストを最小化という問題は、一度すべての点を取り除いたあとで、加える頂点のコストを最大化する問題と言い換えることができる。こちらの方が都合が良いので以下ではこの言い換えた後の問題を解いていく。

まず頂点1から頂点Nまでの単純パスが1通りになるのは、パスに含まれる辺がすべて橋になっているときである。そのようなグラフの頂点は以下の2種類に分類できる。

タイプ1. 1からNへの単純パスに含まれる頂点
タイプ2. それ以外の頂点

ここで1からNへの単純パスが1通りという条件から、タイプ1の頂点からタイプ2の頂点を経由して別のタイプ1にたどりつくことはできない。逆にタイプ2の頂点からタイプ1の頂点に向かうとき、必ず最初にそれぞれの頂点ごとに決まったタイプ1の頂点を通る必要がある。つまりタイプ2の頂点はタイプ1のいずれかひとつの頂点に「属している」ような関係になっている。

ここでもしそれぞれの頂点のタイプが定まっており、さらに単純パスの形もタイプ2の頂点それぞれがどこに属しているかも定まっているとすると、題意を満たす最大の辺の張り方は一意に決定できる。まず単純パス上の辺はもちろん張る必要がある。次に各タイプ1の頂点について、「その頂点＋その頂点に属している頂点」の集合の中では張れるだけ辺を張っていい。逆にここで挙げた以外の辺は張ってはならない（張った瞬間単純パスが1通りであるという条件が満たされなくなる）。辺のコストに負はないので当然張れるだけ張るのが最適なやり方ということになる。

以上を前提とすると、以下のようなbitDPが立つ。

dp(mask, i): 頂点集合maskを既にグラフに取り込んでおり、最後に単純パス上に追加した頂点がiのときの最大コスト

このDPの遷移は「単純パスをひとつ伸ばす」「最後に単純パスに追加した頂点にタイプ2の頂点をくっつける」の2種類である。前者はまだ使ってない頂点を1個くっつけるだけなので普通のbitDPの遷移になる。後者の「タイプ2の頂点をくっつける」とは上で述べたとおり属する頂点を決めてその中で辺を張れるだけ張る処理のことである。これは前者の遷移と異なり複数の頂点が一度に追加されることもありうる。すなわちまだ使われてない頂点集合の、すべての部分集合が遷移先候補となる。部分集合の列挙を適当にやると2^Nを全部列挙して部分になってるか判定の2^N×2^Nになってしまうが、ちゃんとやるテクでちゃんとやると全体で3^Nに抑えられる（部分集合　列挙とかでググるといくつか出てくる）。あとは「その部分集合＋最後に単純パスにくっつけた頂点」の間で張れるだけの辺を張ったときのコストを足せばいいが、これは前計算しておけるのでDPの外でやっておく。

これでO(3^N×N²)とかになるがdp(mask, i)のときiがmaskに含まれてないときとかは飛ばしたりすれば間に合う（解説だとO(3^N×N)なんだけどちゃんと解析するとNが1個落ちたりするんだろうか

感想

どう見てもbitDPの見た目ではあるんだが全然組めなかった。解説を読んで一個一個イメージを積み重ねていくと確かにな～となって、すごいな～となった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    immutable int INF = 1 << 29;
    
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto G = new int[][](N, N);
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1][s[1]-1] = s[2];
        G[s[1]-1][s[0]-1] = s[2];
    }

    int cost_sum = 0;
    foreach (i; 0..N) foreach (j; i+1..N) cost_sum += G[i][j];
    
    auto cost = new int[](1<<N);
    foreach (mask; 0..(1<<N)) {
        foreach (i; 0..N) {
            foreach (j; i+1..N) {
                if (!(mask & (1 << i))) continue;
                if (!(mask & (1 << j))) continue;
                cost[mask] += G[i][j];
            }
        }
    }

    auto dp = new int[][](1<<N, N);
    foreach (i; 0..(1<<N)) dp[i].fill(-INF);
    foreach (i; 0..N) dp[1][0] = 0;

    auto masks = (1<<N).iota.array;
    masks.sort!((a, b) => a.popcnt < b.popcnt);

    foreach (mask; masks) {
        foreach (i; 0..N) {
            if (!(mask & (1 << i))) continue;
            
            foreach (j; 0..N) {
                if (mask & (1 << j)) continue;
                if (G[i][j] == 0) continue;
                dp[mask|(1<<j)][j] = max(dp[mask|(1<<j)][j], dp[mask][i] + G[i][j]);
            }
            
            int comp = (~mask) & ((1 << N) - 1);
            for (int U = (1 << N) - 1; U >= 0; --U) {
                U &= comp;
                dp[mask|U][i] = max(dp[mask|U][i], dp[mask][i] + cost[U|(1<<i)]);
            }            
        }
    }

    int ans = cost_sum - dp[(1<<N)-1][N-1];
    ans.writeln;
}

nebukuro09の日記

AtCoder Regular Contest 078: F - Mole and Abandoned Mine

問題概要

解法

感想

コード (D言語)