正题
题目链接:https://www.luogu.com.cn/problem/P3343
题目大意
给出(n)个点的一张无向图，每条边被修复的时间是([0,1])的一个随机实数，求这张图联通期望时间。
(1leq nleq 10,mleq frac{n(n-1)}{2})
解题思路
这个随机实数好像是用来吓人的（但是概率分布函数好像能搞）
假设修好了(k)条之后恰好联通了，那么期望需要的时间就是(frac{k}{m+1})
好了现在要求恰好在(k)条边修好之后联通的方案，因为每条边修好的先后顺序是完全随机的。
设(f_{S,i})在生成子图(S)中修好了(i)条边是没有联通的方案，(g_{S,i})则表示联通了的方案，(d_{S})表示生成子图(S)的边数。
求(f_{S,i})的话和之前的[集训队作业2013]城市规划思路很向，考虑扩展出一个新的点(k)，那么我们枚举一个包含(k)的联通块(T(kin T,Tsubseteq S))，然后合并这个联通块后其他的乱选，就有方程
[f_{S,i}=sum_{kin T,Tsubseteq S}sum_{j=0}^{min{d_{T},i}}g_{T,j} imes inom{d_{S-T}}{i-j}
]
然后(g_{S,i})不需要专门的方程因为有(f_{S,i}+g_{S,i}=inom{d_S}{i})
然后答案就是
[sum_{i=0}^{m}frac{i}{m+1}(frac{f_{G,i}}{inom{d_G}{i}}-frac{f_{S,i-1}}{inom{d_G}{i-1}})=frac{1}{m+1}sum_{i=0}^mfrac{f_{G,i}}{inom{d_G}{i}}
]
时间复杂度(O(3^nn^2))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=10;
ll n,m,e[1<<N],d[1<<N],g[1<<N][N*N/2],f[1<<N][N*N/2],C[51][51];
signed main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
x--;y--;e[(1<<x)|(1<<y)]++;
}
ll MS=(1<<n);
for(ll s=0;s<MS;s++)
for(ll t=s;t;t=(t-1)&s)
d[s]+=e[t];
C[0][0]=1;
for(ll i=1;i<=50;i++)
for(ll j=0;j<=50;j++)
C[i][j]=(j?C[i-1][j-1]:0)+C[i-1][j];
for(ll s=1;s<MS;s++){
for(ll i=0;i<=d[s];i++){
ll k=s&-s;
for(ll t=(s-1)&s;t;t=(t-1)&s)
if(t&k)
for(ll j=0;j<=min(i,d[t]);j++)
f[s][i]+=g[t][j]*C[d[s-t]][i-j];
g[s][i]=C[d[s]][i]-f[s][i];
}
}
double ans=0;
for(ll k=0;k<=m;k++)
ans+=(double)f[MS-1][k]/C[m][k];
printf("%.6lf
",ans/(double)(m+1));
return 0;
}