神难qwq。配合rqy的博客食用。
首先我们学到有一个概率函数$p(x)$表示某事件发生概率取值小于x的函数。这个函数有什么特点呢？
那就是$int_{-∞}^{∞}p(x)dx=1$
这个是显然的
然后我们令p(x)为首次联通的时间的概率分布函数
这其实等价于生成树的最大权边等于x的概率，对不对（我虚啊，我很可能理解错的）
然后呢，就有一个期望的式子
$EX=int tp(t)dt$
我忘了是为什么了（上午rqy才刚给我讲过，现在就忘了），我太菜了。
然后本题中，期望就是$EX=int_{0}^{1}xp(x)dx$
$=int_{0}^{1}p(x)( int_{0}^{x}1ds)dx$
$=int_{0}^{1}(int_{s}^{1}p(x)dx)ds$
然后我们把括号里面那个玩意设成P(s)好了
所以原式被我们化成了$int_{0}^{1}P(s)ds$
然后……emm等一会我忘了我要干嘛了qwq
……
然后我们设一个$f_{x,S}$表示集合S（S包含1节点）在x时刻前不连通，x时刻恰好联通的概率
因为在x时刻不连通，所以我们考虑它的转移
$f_{x,S}=sumlimits_{1属于S'}^{S'包含于S}(1-f_{x,S'})(1-x)^{T(S',S-S')}$
这什么意思呢？
我们设T(A,B)为A点集和B点集之间的边数。
首先我们看见里面有一个$(1-f_{x,S'})$，这个玩意的意思是
既然我们的S集合要恰好联通，那在这之前S'作为S的一个子集是一定要联通的。而f表示的是不连通的概率，所以就是1-x呗。
而且S'和外界不要联通。
既然S和外界不要联通，那每条边在x时刻不连通的概率是(1-x)，那T条边都不连通的概率就是$(1-x)^{T(S',S-S')}$
所以说$f_{x,S'}$就是这么一个玩意儿。
然后我们把x当成参，就有了$f_{S'}(x)$这么一个东西。
然后……比如说有个全集U
最后我们求的就是这么一个玩意
$int_{0}^{1}f_{U}(x)dx$
然后下面的我就全忘了，顺着rqy的笔迹讲，不过我自己也看不懂是在干嘛qwq
我们设$dp_{S,k}=int_{0}^{1}f_{S}(x)(1-x)^{k}dx$
$=int_{0}^{1}(sumlimits_{1属于S'}^{S'包含于S}(1-f_{S'}(x))(1-x)^{T(S',S-S')})(1-x)^{k}dx$
设t=T(S',S-S')
$dp_{S,k}=sumlimits_{1属于S'}^{S'包含于S}int_{0}^{1}(1-f_{S'}(x))(1-x)^{t+k}dx$
$=sumlimits_{1属于S'}^{S'包含于S}int_{0}^{1}(1-x)^{t+k}-f_{S'}(x)(1-x)^{t+k}dx$
我们发现后面那个玩意等于$dp_{S',t+k}$
就可以搞啦。至于k到底干嘛的，rqy说不表示实际意义，只是用来简化计算，我没听懂。qwq
最后求的答案就是$dp_{U,0}$
然后就是递归搞一搞DP输出。
（当然到考场上如果碰到这道题我倾向于手玩。智商-INFqwq。）
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<cstdlib> #define maxn 11 #define maxm 55 inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } double f[1<<maxn][maxm]; int q[1<<maxn][1<<maxn]; bool vis[1<<maxn][maxm]; double dfs(int state,int t){ if(state==1) return 0; if(vis[state][t]) return f[state][t]; vis[state][t]=1; double &ans=(f[state][t]=.0); for(int sta=(state-1)&state;sta!=state;sta=(sta-1)&state) if(sta&1){ ans+=1.0/(t+q[sta][state&(~sta)]+1); ans-=dfs(sta,t+q[sta][state&(~sta)]); } return ans; } int main(){ int n=read(),m=read(); int Max=1<<n; for(int i=1;i<=m;++i){ int a=read(),b=read(); a--;b--; for(int sta=0;sta<Max;++sta){ if(((sta>>a)&1)==0) continue; for(int stb=0;stb<Max;++stb){ if(((stb>>b)&1)==0) continue; q[sta][stb]++; q[stb][sta]++; } } } printf("%.6lf",dfs(Max-1,0)); return 0; }