记录编号	227696	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015]地震后的幻想乡	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2016-02-18 19:55:51	内存使用	1.95 MiB

#include<stdio.h>
int n,m,maxn,e[11],sz[1<<11],cnt[1<<11];
long long c[55][55],f[1<<11][55],g[1<<11][55];
double ans;
void DP(){
	for(int s=1;s<maxn;++s){
		sz[s]=sz[s>>1]+(s&1);//sz[s]代表s集合中点的数量
		if(sz[s]==1){//若s未单独一个点，显然方案数为1
			g[s][0]=1;
			continue;
		}
		for(int i=0;i<n;++i)
		    if((s>>i)&1)//更新当前s集合的边数
		        cnt[s]+=sz[e[i]&s];
		cnt[s]>>=1;//因为是双向边，所以除以2
		int lowbit=s&-s;
		for(int t=(s-1)&s;t;t=(t-1)&s)//枚举s的真 ・子集
		    if(t&lowbit)//从s里取一定点，这样方案数就不重不漏了！
		        for(int i=0;i<=cnt[t];++i)
		            for(int j=0;j<=cnt[s^t];++j)
		                f[s][i+j]+=g[t][i]*c[cnt[s^t]][j];
		for(int i=0;i<=cnt[s];++i)
		    g[s][i]=c[cnt[s]][i]-f[s][i];
	}
}
int main(){
	freopen("zjoi15_mst.in","r",stdin);
	freopen("zjoi15_mst.out","w",stdout);
	int u,v;scanf("%d%d",&n,&m);maxn=1<<n;
	for(int i=0;i<m;++i) scanf("%d%d",&u,&v),--u,--v,e[u]|=1<<v,e[v]|=1<<u;
	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];
	}
	DP();
	for(int i=0;i<=m;++i) ans+=(double)f[maxn-1][i]/c[cnt[maxn-1]][i];
	ans/=m+1;//答案的计算方式很特别，是一个逐步累加的过程！
	printf("%.6lf",ans);
	//while(1);
}