P3343 [ZJOI2015] 地震后的幻想乡

, , , ,

Description

https://www.luogu.com.cn/problem/P3343

Solution

相当妙妙的题目啊。

根据提示，就直接把第 $k$ 大权值设为 $\dfrac{k}{m+1}$。

考虑恰好选 $k$ 条边使图联通的概率 $g_k$，则答案为 $\sum\limits_{i=1}^m \dfrac{ig_i}{m+1}$。

恰好是不好做的，转化为选 $k$ 条边依然不能使图联通的概率 $f_k$，则答案为 $\sum\limits_{i=0}^m \dfrac{f_i}{m+1}$。

观察到点比较少，记 $f_{S,i}$ 表示点集为 $S$，选了 $i$ 条边依然不能使图联通的个数。考虑容斥转移，记 $x$ 是 $S$ 中最小的一个点（其实可以是任意一个点，但是为了方便），枚举包含 $x$ 的连通块，然后枚举联通块选了几条边，钦定这个连通块一定联通，而连通块的在 $S$ 补集中的边随便选，两个连通块之间没有边。这样可以找到不连通的全部情况。这种容斥的想法真是很妙啊！！！

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int mod=1e9+7;
double dp[(1<<10)+5][105],c[105][105],ans;
struct yyy{
	int x,y;
}e[105];
int n,m,g[(1<<10)];
signed main(void){
//	freopen("1.in","r",stdin);
	int i,j,k,t;
	read(n);read(m);
	for (i=1;i<=m;i++) read(e[i].x),read(e[i].y),e[i].x--,e[i].y--;
	for (i=0;i<(1<<n);i++) 
		for (j=1;j<=m;j++)
			if ((i>>e[j].x)%2&&(i>>e[j].y)%2) g[i]++;
	for (i=0;i<=m;i++) {
		c[i][0]=1;
		for (j=1;j<=i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j];
	}
	int N=(1<<n);
	for (i=1;i<N;i++) {
		int z=min(n+1,__builtin_ctz(i));
		for (t=i&(i-1);t;t=(t-1)&i) if ((t>>z)&1) {
			for (j=0;j<=g[i^t];j++) {
				for (k=0;k<=g[t];k++)
					dp[i][j+k]+=(1-dp[t][k])*c[g[t]][k]*c[g[t^i]][j]/c[g[i]][j+k];//这j+k条边并没有先后顺序
			}
		} 	
	}
	for (i=0;i<=m;i++) ans+=dp[N-1][i]/(m+1);
	printf("%.6lf",ans);
	return 0;
}