仍然是自闭的%
首先hint给了一个提示，对于n个[0,1]之间的随机变量x1,x2,...,xn，第k小的那个的期望值是k/(n+1)
题目问的是最小生成树中最大边的e的期望，可以转化成最大边在所有边的期望排名*(m+1)
设p(i)为刚好i条边就能够把所有点连起来的概率
e(期望) = 1/m+1 * sigema(1~m) i*p(i)
= 1/m+1 * sigema(1~m)i sigema(j>=i)p(j)
sigema(j>=i)p(j)就是p的后缀和，等同于用i-1条边不能够把所有点连在一起的概率，令其为h(i-1)
e(期望) = 1/m+1 * sigema(0~m-1) h(i)
概率我们可以用i条边不能够把所有点连在一起的方案数f(i)除以用i条边随机出现的方案数计算
e(期望) = 1/m+1 * sigema(0~m-1) f(i)/C(m,i)
现在就要解决如何计算用i条边不能够把所有点连在一起的方案数
设f[0][i][zt]表示用了i条边，不能够把为zt的点集都连在一起，1表示可以
f[0][i][zt]= sigema(zt的子集tzt) sigema(j<i) f[1][j][tzt]*C[tot[zt^tzt]][i-j]
意思是选择一个联通的子集用了j条边，剩下的边乱选（可以保证不会和tzt里面的点相连，也就是说tzt这个块是独立出来的）
然后我们会发现一个问题，乱选的时候也有可能连出另一个联通块，这样会和枚举到这个子集的时候的计算重复 所以我们枚举子集的时候需要加一个条件，我们只用某一个点位于的联通块来更新答案
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; LL C[110][110]; void initC(int m) { 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-1]+C[i-1][j]; } } int tot[1100]; struct edge{int x,y;}e[110]; void inittot(int n,int m) { int li=(1<<n)-1; for(int zt=1;zt<=li;zt++) { tot[zt]=0; for(int i=1;i<=m;i++) if(((1<<e[i].x-1)&zt)&&((1<<e[i].y-1)&zt)) tot[zt]++; } } LL f[2][110][1100];//是否联通，用了的边数，点集 int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y); initC(m);inittot(n,m); int li=(1<<n)-1; for(int i=1;i<=n;i++)f[1][0][1<<i-1]=1; for(int zt=1;zt<=li;zt++) { int xt=(zt&-zt); for(int tzt=((zt-1)&zt);tzt;tzt=((tzt-1)&zt)) if(tzt&xt) for(int i=0;i<=tot[zt];i++) { int tli=min(i,tot[tzt]); for(int j=0;j<=tli;j++) f[0][i][zt]+=f[1][j][tzt]*C[tot[zt^tzt]][i-j]; f[1][i][zt]=C[tot[zt]][i]-f[0][i][zt]; } } double ans=0; for(int i=0;i<m;i++)ans+=double(f[0][i][li])/C[m][i]; printf("%.6lf ",ans/(m+1)); return 0; }