「ZJOI2015」地震后的幻想乡

/*
难度最低的解法 

钦定一个边集S作为前S小如果这个边集假如第|S|小这条边时加入时S恰好联通， 那么我们就能够算出他的贡献了

恰好联通 = 加了这条边之前不连通方案数 - 加了这条边之后不连通方案数

然后考虑dp联通不连通的状态

f[S][i], g[S][i] 分别表示点集为S用了i条边， 不联通和连通的方案数

显然 F[S][i] + g[S][i] = \binom{bian_S}{i}

然后就可以子集dp转移了F[S][i] = \sum{T \subseteq S } \sum_{j = 0}{bian_T} g[T][j] * \binom{S - T, i - j}

当然是要固定点防止算重的

 最后统计答案就是 \frac{1}{m + 1} \sum_{k = 1}^{m} \frac{f[U][k]}{\binom{m}{k}}
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define M 10
#define mmp make_pair
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}

double f[1 << 10][51], g[1 << 10][51], c[51][51], ans;
int n, m, bian[1 << 10], note[51][51];

int main() {
    n = read(), m = read();
    c[0][0] = 1;
    for(int i = 1; i <= m; i++) {
        c[i][0] = 1;
        for(int j = 1; j <= m; j++) {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    for(int i = 1; i <= m; i++) {
        int vi = read() - 1, vj = read() - 1;
        note[vi][vj] = note[vj][vi] = 1;
    }
    for(int s = 1; s < (1 << n); s++) {
        int x = -1, tot = 0;
        for(int i = 0; i < n; i++) {
            if((s & (1 << i)) == 0) continue;
            if(x == -1) x = i;
            else {
                if(note[x][i]) tot++;
            }
        }
        bian[s] = bian[s - (1 << x)] + tot;
    }
    for(int s = 1; s < (1 << n); s++) {
        for(int i = 0; i <= bian[s]; i++) {
            for(int t = s; t; t = (t - 1) & s) {
                if(t & (s & -s)) {
                    for(int j = 0; j <= min(i, bian[t]); j++) {
                        f[s][i] += g[t][j] * c[bian[s - t]][i - j];
                    }
                }
            }
            g[s][i] = c[bian[s]][i] - f[s][i];
        }
    }
    for(int i = 0; i <= m; i++) ans += f[(1 << n) - 1][i] / c[m][i];
    ans /= 1.0 * (m + 1);
    printf("%.6lf\n", ans);
    return 0;
}

「ZJOI2015」地震后的幻想乡

原文：https://www.cnblogs.com/luoyibujue/p/10506879.html