思路
$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;
}