Luogu P3343

思路

$p(x)$为在时间$x$时图联通的概率，$P(x)$为时间$x$后图联通的概率，即$P(x)=\int_x^1p(x)\text{d}x$
$$\begin{split}\text{ans}
&=\int_0^1p(x)x\text{d}x\\
&=\int_0^1p(x)\int_0^x\text{d}t\text{d}x\\
&=\int_{0}^1\int_x^1p(t)\text{d}t\text{d}x\\
&=\int_{0}^1P(x)\text{d}x
\end{split}$$

设$P_{S}(x)(1\in S)$为点集$S$在时间$x$后联通的概率。那么就可以枚举一个点集$S_0(1\in S_0)$，钦定$S_0$内部联通，$S_0$中的所有点与$\complement_{S}S_0$中的所有点都不联通，进行转移。设$T(S_0, S_1)$表示两个$S_0, S_1$之间边的数目，则有

$$P_S(x)=\sum \limits_{1\in S_0\subset S}(1-x)^{T(S_0, \complement_SS_0)}\cdot (1-P_{S_0}(x))$$

那么对于点集$S(1\in S)$答案就是
$$\begin{split}\text{ans} &=\int{0}^1P_S(x)\text{d}x\\
&=\int_0^1\sum \limits_{1\in S_0\subset S}(1-x)^{T(S_0, \complement_SS_0)}\cdot (1-P_{S_0}(x))\text{d}x\\
&=\sum \limits_{1\in S_0\subset S}\left(\int_0^1(1-x)^{T(S_0, \complement_SS_0)}\cdot (1-P_{S_0}(x))\text{d}x\right)\\
&=\sum \limits_{1\in S_0\subset S}\left(\int_0^1(1-x)^{T(S_0, \complement_SS_0)} \text{d}x-\int_0^1(1-x)^{T(S_0, \complement_SS_0)} \cdot P_{S_0}(x)\text{d}x\right)\\
&=\sum \limits_{1\in S_0\subset S}\left(\frac{1}{1+T(S_0, \complement SS_0)}-\int_0^1(1-x)^{T(S_0, \complement_SS_0)} \cdot P{S_0}(x)\text{d}x\right)\\
\end{split}$$

其中，$$\begin{split}
&\ \ \ \int_0^1(1-x)^k \cdot P_{S}(x)\text{d}x\\
&=\int_0^1\cdot\sum \limits_{1\in S_0\subset S}(1-x)^{k+T(S_0, \complement_SS_0)}\cdot (1-P_{S_0}(x))\text{d}x \\
&=\sum \limits_{1\in S_0\subset S}\left(\int_0^1(1-x)^{k+T(S_0, \complement_SS_0)}\cdot (1-P_{S_0}(x))\text{d}x\right)\\
&=\sum \limits_{1\in S_0\subset S}\left(\frac{1}{1+k+T(S_0, \complement SS_0)}-\int_0^1(1-x)^{k+T(S_0, \complement_SS_0)} \cdot P{S_0}(x)\text{d}x\right)\\
\end{split}$$

所以设$$f_{S, k}=\int_0^1(1-x)^k \cdot P_{S}(x)\text{d}x$$

很容易得到递推式$$f_{S, k}=\sum \limits_{1\in S_0\subset S}\left(\frac{1}{1+k+T(S_0, \complement_SS_0)}-f_{S_0, k+T(S_0, \complement_{S}S_0)}\right)$$

其中，边界条件很显然为$f_{\{1\}, k}=0$

直接记搜就可以了

代码

#include <iostream>
#include <cstdio>

template <typename T> void in(T &_){
    char c=getchar(); while(c<'0'||c>'9') c=getchar();
    _=0; while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar();
}
template <typename T, typename ...A> void in(T &_, A &...a){in(_); in(a...);}

double f[1<<10][46];
int N, M, x[55], y[55];

double dfs(int sta, int K){
    if(sta==1) return 0;
    if(f[sta][K]>0) return f[sta][K];
    int s1=(sta>>1);
    for(int s0=(s1-1)&s1; ; s0=(s0-1)&s1){
        int s=(s0<<1)|1, t=0;
        for(int i=1; i<=M; i++) 
            if(((sta>>(x[i]-1))&1)&((sta>>(y[i]-1))&1))
                if(((s>>(x[i]-1))&1)^((s>>(y[i]-1))&1))
                    t++;
        f[sta][K]+=1.0/(1.0+t+K)-dfs(s, K+t);
        if(!s0) break;
    }
    return f[sta][K];
}

int main(){
    in(N, M);
    for(int i=1; i<=M; i++) in(x[i], y[i]);
    printf("%.6lf\n", dfs((1<<N)-1, 0));
    return 0;
}