問題概要

頂点数 $N$ 、辺数 $M$ の単純無向グラフが与えられます。また $0$ 以上 $100$ 以下の整数 $p$ が与えられます。

グラフの各辺は $p$ % の確率でそれぞれ独立に消失します。グラフ全体が連結である確率を求めてください。

制約

$1 \le N \le 14$
$0 \le M \le 100$
$0 \le P \le 100$

考えたこと

$M \le 100$ なので、辺の消失パターン ( $2^{M}$ 通りある) すべてを調べる方法では間に合わない。

しかしながら、このようにグラフ上の指数探索系の問題では、「ある頂点 $v$ を一つ固定して、その周りの様子で場合分けする」のが定石だと思われる。ここでは、頂点 $v$ を含む連結成分 $S$ がどのようになるかで場合分けする考え方で問題を解いていこう。ここで、

$f(S)$ = もとのグラフのうち、頂点集合を $S$ のみに限ったグラフを考えたとき、それが連結になる確率

とする。これを求める漸化式を立てていく。なお答えは $f(V)$ と表される。

$f(S)$ を求める漸化式

$f(S)$ をいきなり求めることが難しいので、余事象を考えて全体から引くことを考えよう。つまり、 $v \in T \subsetneq S$ であるような $T$ をすべて考えて引いていく方針で考えてみよう。

$f(S)$ を求めるために、 $v \in S$ となる頂点 $v$ を選び、 $S$ 内部で $v$ を含む連結成分 $T$ で場合分けして考えることにすると、

$f(S) = 1.0 - \sum_{v \in T \subsetneq S} f(T) \times p^{|C(T, S-T)|}$

となる。ここで $C(X, Y)$ は、頂点集合 $X$ と頂点集合 $Y$ との間にある辺集合を表します。

これは「部分集合の部分集合」を考えていくような遷移になっているので、 $O(3^{N})$ な bit DP となります。なお、 $C$ については、頂点集合 $S$ に含まれる辺の本数を $C(S)$ として、

$C(X, Y) = e(X \cup Y) - e(X) - e(Y)$

と求められます。 $e$ については $O(N 2^{N})$ で計算できます。

drken1215.hatenablog.com

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, M;
    double P;
    cin >> N >> M >> P;
    P /= 100;
    vector<vector<bool>> G(N, vector<bool>(N, false));
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a][b] = G[b][a] = true;
    }

    // P の冪乗を確保しておく
    vector<double> power(M + 1, 1);
    for (int i = 0; i < M; ++i) power[i+1] = power[i] * P;

    // e(S) を求める
    vector<long long> e(1<<N, 0);
    for (int u = 0; u < N; ++u)  {
        for (int v = 0; v < N; ++v) {
            if (G[u][v]) {
                int S = (1<<u) | (1<<v);
                e[S] = 1;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int S = 0; S < (1<<N); ++S) {
            if (S & (1<<i)) {
                e[S] += e[S ^ (1<<i)];
            }
        }
    }

    // O(3^N) DP
    vector<double> f(1<<N, 1.0);
    for (int S = 1; S < (1<<N); ++S) {
        // S に含まれる頂点 v を 1 つ選ぶ
        int v = -1;
        for (v = 0; v < N; ++v) if (S & (1<<v)) break;

        // S の部分集合を走査
        for (int T = S - 1; T >= 0; --T) {
            T &= S;

            if (T & (1 << v)) {
                int c = e[S] - e[T] - e[S - T];
                f[S] -= f[T] * power[c];
            }
        }
    }
    cout << fixed << setprecision(10) << f[(1<<N)-1] << endl;
}