「ZJOI2015」地震后的幻想乡

「ZJOI2015」地震后的幻想乡

题意：给定一张图，每条边的边权在 \([0,1]\) 中随机，求最小生成树的最大边权的期望。其中这个很重要：对于 \(n\) 个 \([0,1]\) 之间的随机变量，第 \(k\) 小的那个的期望值是 \(\frac{k}{n+1}\)

那暴力就很容易了，假设我们已经按边权从小到大排好了序，也就是相当于全排列枚举这 \(m\) 条边，枚举出来的第 \(i\) 条边的边权就是第 \(i\) 小的，直接跑 \(Kruskal\)，如果在第 \(i\) 条边恰好联通，答案加上 \(\frac{i}{m+1}\)，最后再除以总的方案数 \(m!\) 即可

考虑优化，记 \(P(i)\) 为第 \(i\) 条边恰好联通的概率，那么 \(ans= \sum_{i=1}^{m} i \times P(i)\)，那么现在就是考虑恰好在第 \(i\) 边连接的方案数了，因为总的方案数很好求，一个组合数就可以了

而恰好联通方案\(=\)加之前不连通方案\(-\)加之后不连通方案，而 \(n\) 又这么小，考虑状态压缩，记 \(dp_{s,i,0/1}\) 表示选的点集为 \(s\)，选了 \(i\) 条边，不连通\(/\)联通的方案数，\(cnt_s\) 表示点集 \(s\) 中的边数，肯定有 \(dp_{s,i,0}+dp_{i,s,1}={cnt_s \choose i}\)

发现联通的不太好搞，考虑求出不连通的，再用上面那个式子去求；肯定需要枚举子集的，然后可以让方案数加上一部分联通、另外一部分乱选的乘积，就像括号序列那道题目一样一部分全部括起来、另外一部分随意一样；但是会发现还是会重复，因为另外一部分是完全乱选，那我们可以钦定一个点必须在子集中，就像一个分割线，慢慢扩大，这样就不会重复了

考虑求答案，\(P(i)=\frac{i}{m+1} \times (\) 加第 \(i\) 条边前联通的概率 \(-\) 加第 \(i\) 条边后联通的概率 \()\)

其实这道题目也不是不可以斯特林反演或者积分做

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,cnt[1025],val[1025];
long long c[101][101],dp[1025][101][2];
double res;
int count(int x){
	int res=0;
	while(x) res+=x&1,x>>=1;
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		val[(1<<(x-1))|(1<<(y-1))]++;
	}
	for(int i=1;i<(1<<n);i++){
		for(int j=i;j;j=i&(j-1)) cnt[i]+=val[j];
	}
	for(int i=1;i<=100;i++){
		c[i][0]=c[0][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	for(int i=1;i<(1<<n);i++){
		if(count(i)==1){
			dp[i][0][0]=0;
			dp[i][0][1]=1;
			continue;
		}
		for(int j=i&(i-1);j;j=i&(j-1)){
			if(!(j&(i&-i))) continue;
			for(int l=0;l<=cnt[j];l++){
				for(int k=0;k<=cnt[i^j];k++) dp[i][l+k][0]+=dp[j][l][1]*c[cnt[i^j]][k];
			}
		}
		for(int j=0;j<=cnt[i];j++) dp[i][j][1]=c[cnt[i]][j]-dp[i][j][0];
	}
	for(int i=1;i<=m;i++) res+=1.0*i/(m+1)*(1.0*dp[(1<<n)-1][i-1][0]/c[cnt[(1<<n)-1]][i-1]-1.0*dp[(1<<n)-1][i][0]/c[cnt[(1<<n)-1]][i]);
	printf("%.6lf",res);
	return 0;
}