【BZOJ3925】[ZJOI2015]地震后的幻想乡（动态规划）

时间：2021-09-05 07:26:40

【BZOJ3925】[ZJOI2015]地震后的幻想乡（动态规划）

题面

BZOJ

洛谷

题解

题目里面有一句提示：对于\(n\)个\([0,1]\)之间的随机变量\(x1,x2,...,xn\)，第\(k\)小的那个的期望值是\(k/(n+1)\)。

显然要求的东西就是一棵最小生成树最大边的期望。而求解最小生成树只需要知道边的排名以及当前点之间的连通性。因为我们知道第\(k\)小的值的期望，所以我们只需知道最小生成树做到了第几条边时联通。那么需要求解的只有在连完第\(k\)条边只有连通的方案数了。

预处理点集内部的方案数，假设为\(cnt(S)\)，设\(f[i][S][0/1]\)表示对于点集\(S\)而言，选择了其中\(i\)条边之后连通或者不连通的方案数。

首先很显然，连通和不连通的方案数总和就是任意选择边的方案数。

即\(\displaystyle f[i][S][0]+f[i][S][1]={cnt(S)\choose i}\)。

那么考虑如何计算\(dp\)值。

如果我们要算不连通的方案数，那么我们枚举其中一个定点所在的连通块，那么这个连通块不能和其他点之间有连边，可以得到转移：\(\displaystyle f[i+j][S][0]=\sum f[i][T][1]*{cnt(S-T)\choose j}\)

而连通的方案数则直接用前面那个总方案减去不连通的就好了。

那么最终计算答案的时候，枚举用了几条边\(\displaystyle ans=\frac{1}{m+1}\sum_{i=0}^m \frac{f[i][All][0]}{m\choose i}\)

#include<iostream>

#include<cstdio>

using namespace std;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,S,bul[1<<10],cnt[1<<10],G[10],lg[1<<10];

long long f[50][1<<10][2],C[50][50];

double ans;

int lb(int x){return x&(-x);}

int main()

{

	n=read();m=read();S=1<<n;

	for(int i=0;i<=m;++i)C[i][0]=1;

	for(int i=1;i<=m;++i)

		for(int j=1;j<=i;++j)

			C[i][j]=C[i-1][j-1]+C[i-1][j];

	for(int i=1;i<S;++i)bul[i]=bul[i>>1]+(i&1);

	for(int i=2;i<S;++i)lg[i]=lg[i>>1]+1;

	for(int i=1,u,v;i<=m;++i)u=read()-1,v=read()-1,G[u]|=1<<v,G[v]|=1<<u;

	for(int i=1;i<S;++i)cnt[i]=cnt[i^lb(i)]+bul[G[lg[lb(i)]]&i];

	for(int i=1;i<S;++i)f[0][i][bul[i]==1]=1;

	for(int i=1;i<=m;++i)

		for(int T=1;T<S;++T)

		{

			int TT=T^lb(T),u=lb(T);

			for(int P=(TT-1)&TT;;P=(P-1)&TT)

			{

				for(int j=0;j<=i;++j)f[i][T][0]+=f[j][P|u][1]*C[cnt[TT^P]][i-j];

				if(!P)break;

			}

			f[i][T][1]=C[cnt[T]][i]-f[i][T][0];

		}

	for(int i=0;i<=m;++i)ans+=1.0*f[i][S-1][0]/C[m][i];

	ans/=m+1;printf("%.6lf\n",ans);

	return 0;

}

相关文章