「ZJOI2015」地震后的幻想乡
前言：
想了很久，最后只能失败告终。
基本分析到了一半，只是没有将其转化为古典概型后考虑求解方案数。
说实话有点可惜……
题意：
给定一张 \(n\) 个点 \(m\) 条边的无向连通图，每条边的边权是 \([0,1]\) 之间的随机实数，求其最小生成树上最大边权的期望值。
数据范围：\(n \le 10\)，无重边与自环。
提示：对于 \(n\) 个 \([0,1]\) 之间的随机变量 \(x_1,x_2,\cdots,x_n\)，第 \(k\) 小的那个的期望值是 \(\frac{k}{n+1}\)。
思路：
首先根据题目提示我们可以猜到我们需要求解最后的最小生成树上最大边的排名的期望值。
（P.S 这里的排名指的是 \(m\) 条边的边权大小排名。）
这个值不好求，我们想到期望的定义是加权平均。
我们可以枚举最大边排名为 \(i\) 的情况，然后将其加权平均。
也就是 \(ans = \sum\limits_{i=1}^{m} E(i)P(L = i)\)，其中 \(P(L = i)\) 表示最大边排名为 \(i\) 的概率，\(E(i)\) 表示的是当排名为 \(i\) 时的期望值。
然后求解最大边排名为 \(i\) 的概率，实质上我们要考虑的是将前 \(i\) 小的边全部加入后，图恰好联通的概率。
这个时候发现我们将实数的取值变成了排名。
此时的题目是一个古典概型，能够通过求解方案数得到概率。
因此我们继续考虑方案数怎么求。
此时我们对于一个点集进行思考，考虑这一个点集一共使用了 \(x\) 条边联通起来的情况。
我们设 \(F(S,x)\) 表示点集 \(S\) 用了 \(x\) 条边使得 \(S\) 联通的方案数。
一个点集要么联通要么不联通……
那么设 \(G(S,x)\) 表示不联通的方案数，则 \(F(S,x) + G(S,x) = \dbinom{cnt_S}{x}\)，其中 \(cnt_S\) 表示点集 \(S\) 中有多少条边。
接下来我们就需要考虑怎么使用 \(F\) 和 \(G\) 表示出我们所需的答案。
考虑到 \(ans = \sum\limits_{i=1}^{m} E(i)P(L = i)\)。
根据题目的提示，我们可以简单地把上面的式子转化一下：
\[ans = \sum\limits_{i=1}^{m} \dfrac{i \times P(L = i)}{m + 1} \]这是很显然的，我们设 \(H = \sum\limits_{i=1}^{m} i \times P(L = i)\)：
那么很容易发现 \(H = \sum\limits_{i=1}^{m} P(L \ge i)\)。
这个时候我们就要让前 \(i\) 小的边无法联通，也就达成了最大边在 \(i\) 及其之后的目的。
也就是 \(H=\sum\limits_{i=1}^{m} \dfrac{G(S,i - 1)}{tot}\)，其中 \(tot\) 是总方案数。
于是题目很明了了，我们需要求解 \(G\)。
实现：
考虑 \(G\) 如何求解。
这里我们考虑 \(S\) 的子集，\(S\) 必定会从子集 \(T\) 转移而来。
为了要使得 \(S\) 不联通，很容易想到使得 \(T\) 和 \(S - T\) 不联通。
那么我们只需要让所有选择的边都在 \(S - T\) 内不就行了？
这样一定不联通，状态转移方程就能够写出来：
\[G_{S,x} = \sum\limits_{T \in S,0 \le x \le m,0 \le y \le x} F_{T,y}\times \dbinom{cnt_{S-T}}{x-y} \]然后根据 \(F(S,x) + G(S,x) = \dbinom{cnt_S}{x}\) 计算 \(F(S,x)\) 即可。
细节：
- 1.子集枚举
这个知识点不难，但是我觉得有必要拉出来讲讲。
状态压缩的时候，对于一个状态 \(S\)，我们有时需要去枚举它的子集，如果暴力枚举会直接让时间复杂度乘上一个平方，这显然是不行的。
那么我们怎么优化？
考虑如何不重不漏地遍历当前状态的所有子集。
想到 \(S\) 的子集所对应的二进制数是一定小于 \(S\) 的，那么我们就可以通过将 \(S\) 递减来枚举子集。
在递减的时候，有时当前递减到的状态中出现了一些 \(S\) 中不存在的 1。
这些 1 其实可以直接去掉，因为递减的过程中会不断去掉这些 1，直接将其去掉依旧能够保证不重不漏。
因此我们就写出了直接枚举所有子集的代码：
for (int S = 1; S <= tot; S++) {
for (int T = (S - 1)&S; T; T = (T - 1)&S) {
//写点什么...
}
}
- 2.DP转移
这里我们涉及到的DP比较特殊，因为我们在计算的是不连通方案。
按照我们的思路想来看上去没有问题，但实际上计算的时候会发现算重了。
因为什么？在我们计算的时候会发现可能有一些方案选择的边是相同的，但是对应的 \(T\) 不一样。
这时我们简单模拟一下会发现对应的这些 \(T\) 中不存在公共点并且将 \(S\) 完全覆盖，因此我们提前在 \(S\) 中指定一个点 \(p\)，强制要求 \(T\) 中包含 \(p\) 即可做到不重不漏的计数。
代码（由LOJ格式化）：
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
#define ll long long
ll F[1 << N][N * N], G[1 << N][N * N], C[N * N][N * N];
int cnt[1 << N];
bool e[N][N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--, b--;
e[a][b] = e[b][a] = true;
}
int tot = (1 << n) - 1;
//预处理 cnt
for (int i = 1; i <= tot; i++) {
for (int j = 0; j < n; j++)
if ((i >> j) & 1)
for (int k = j + 1; k < n; k++)
if (((i >> k) & 1) && e[j][k])
cnt[i]++;
}
//预处理组合数
C[0][0] = 1;
for (int i = 1; i <= m; i++)
for (int j = 0; j <= i; j++)
if (j == 0)
C[i][j] = 1;
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
//DP！
for (int S = 1; S <= tot; S++) {
int sz = 0; //计算当前集合有多少个点
int p = 0; //不重不漏
for (int i = 0; i < n; i++)
if ((S >> i) & 1)
sz++, p = (1 << i);
if (sz == 1) { //只有一个点，直接联通
F[S][0] = 1;
continue;
}
for (int T = (S - 1)&S; T; T = (T - 1)&S) {
if (!(T & p))
continue; //这里有常数优化，因此看上去有所差别
for (int x = 0; x <= cnt[S] + cnt[S - T]; x++)
for (int y = 0; y <= cnt[T]; y++)
if (x - y <= cnt[S - T])
G[S][x] += F[T][y] * C[cnt[S - T]][x - y];
}
for (int i = 0; i <= m; i++)
F[S][i] = C[cnt[S]][i] - G[S][i];
}
double ans = 0;
for (int i = 0; i <= m; i++)
ans += G[tot][i] / (double)C[cnt[tot]][i]; //总方案数就是 C(cnt[tot],i)
printf("%.6lf", ans / (double)(m + 1));
return 0;
}
上面的代码的时间复杂度为 \(O(3^n m^2)\)，其中子集枚举的时间复杂度是 \(O(3^n)\)，可由二项式定理简单证得。
根据评测结果来看，效率比较优秀。
标签：幻想,联通,limits,sum,枚举,子集,地震,ZJOI2015,我们 From： https://www.cnblogs.com/XiaoShanYunPan/p/17777781.html