BZOJ 3925 ZJOI2015 地震后的幻想乡

假设我们用了边权前i小的边使得图连通，那么对答案的贡献为i/m+1

又因为期望的线性性质，我们只需要求用了i条边就可以了

不妨设g(S)(i)表示用了i条边使得点集S连通的概率

设f(S)(i)表示用了i条边使得点集S没有连通的概率

设cnt(S)表示点集S内部的边的数量

我们可以知道f(S)(i)+g(S)(i)=C( cnt(S),i )

那么我们只需要求出f(S)(i)就可以了

设now是S中的一个点，设T是S的子集且包含now

f(S)(i)=sigma( g(T)(i-j) * C( cnt(S-T),j ) )

之后我们考虑对于答案的计算，设全集为S

对于f(S)(i)，对于答案的贡献为 (i+1)/(m+1)-i/m+1 =1/m+1

累加即可

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int maxn=10;
int n,m,u,v,lim;
LL f[1<<maxn][52];
LL g[1<<maxn][52];
LL cnt[1<<maxn];
LL C[52][52];
int s[maxn],Num[1<<maxn];

void pre_C(){
 	C[0][0]=1;
 	for(int i=1;i<=m;++i){
 		C[i][0]=C[i][i]=1;
 		for(int j=1;j<i;++j){
 			C[i][j]=C[i-1][j-1]+C[i-1][j];
		 }
	 }return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		u--;v--;
		s[u]|=(1<<v);s[v]|=(1<<u);
	}pre_C();lim=(1<<n)-1;
	for(int S=1;S<=lim;++S){
		Num[S]=Num[S>>1]+(S&1);
		if(Num[S]==1){g[S][0]=1;continue;}
		for(int i=0;i<n;++i){
			if(S>>i&1)cnt[S]+=Num[s[i]&S];
		}cnt[S]>>=1;
		int now=(S&(-S));
		for(int T=(S&(S-1));T;T=((T-1)&S)){
			if(T&now){
				for(int i=0;i<=cnt[S];++i){
					for(int j=0;j<=i&&j<=cnt[S^T];++j){
						f[S][i]+=g[T][i-j]*C[cnt[S^T]][j];
					}
				}
			}
		}
		for(int i=0;i<=cnt[S];++i)g[S][i]=C[cnt[S]][i]-f[S][i];
	}
	double ans=0;
	for(int i=0;i<=m;++i)ans+=(double)(f[lim][i])/C[m][i];
	ans/=m+1;
	printf("%.6lf
",ans);
	return 0;
	
}