地震后的幻想乡

终于把这个坑给填上了。。。数学不好真的难受,得好好补一下了

0x00 题意

给定一个 $n$ 个点,$m$ 条边的无向图,每条边的边权在 $[0,1]$之间随机均匀分布,求这个图的最小生成树的最大边权的期望。

0x01 翻译

卧槽,这TMD能做?

我们需要翻译一下。。。

提示:

(以下内容与题意无关,对于解题也不是必要的。)

对于$n$个$[0,1]$之间的随机变量$x_1,x_2,…,x_n$,第k小的那个的期望值是$k/(n+1)$。

考虑上面的文字,反正都是期望嘛,不妨我们就把这 $m$ 条边的边权看成 $i/(m+1)$,

于是现在的题意变成了这个样子:

给定一个 $n$ 个点,$m$ 条边的无向图,每条边都有一个排名,求最小生成树上最大排名的期望。

0x02 我会全排列!

有一个智障的想法。。。我们随机给每条边一个排名,暴力求解最小生成树,多求几次不就成了期望辣?

现在暴力枚举 $m!$ 种可能的情况,暴力给每条边赋一个权值,暴力求解最小生成树,最后求个平均数就是期望辣!

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
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

inline int read(int u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

const int maxn = 12;

struct MFS {
int fa[maxn]; void clear(int n) { for (int i = 0; i <= n; i++) fa[i] = i; }
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
} mfs;

pair<int,int>e[maxn * maxn];

int main() {
int n = read(), m = read();
for (int i = 1; i <= m; i++)
e[i].first = read(), e[i].second = read();
sort(e + 1, e + 1 + m);
double ans = 0;
do {
mfs.clear(n);
for (int i = 1, j = n; i <= m; i++) {
if (mfs.find(e[i].first) != mfs.find(e[i].second))
mfs.merge(e[i].first, e[i].second), j--;
if (j == 1) { ans += 1.0 * i / (m + 1); break; }
}
} while (next_permutation(e + 1, e + 1 + m));
for (int i = 1; i <= m; i++) ans /= i;
printf("%.6lf", ans);
}

实测可以拿到 $35$ 分的好成绩,这样的暴力在考场上还是蛮不错了

0x03 我数学吊打Anoxiacxy!

如果你的实力满足以上的条件,那么还可以这么干啦!%%%rqy

显然,如果我们知道了一个值 $x$,表示当前的最大边权,那么所有的边就可以被分为两类:即 $w_i > x$的和$w_i\leq x$的,设 $p(x)$ 为最大边权为$x$ 时,能够连通的概率。

那么,我们要求的期望值 $E = \int_0^1p(x)xdx$

这里有一个 $trick$,可以容斥一下,设 $P(t)=\int_x^1p(x)dx$,即在最大边权大于 $t$ 时连通的概率。
$$
\begin{aligned}
E &= \int_0^1p(x)xdx \\
&=\int_0^1p(x)\int_0^x1dtdx\\
&=\int_0^1\int_t^1p(x)dxdt\\
&=\int_0^1P(t)dt
\end{aligned}
$$
然后就去掉了烦人的 $x$ 那一项,既然 $P(t)$ 表示在边权大于$t$时连通的概率,那么也可以认为就是边权等于$t$时不连通的概率。

现在我们来定义一下什么叫做连通,什么叫做不连通,方便起见,当前考虑范围内的点用集合 $S$ 表示。

  • 集合 $S= \{1\}$ 是连通的
  • 如果集合 $S​$ 不是连通的,那么集合 $S​$ 不连通
  • 如果集合 $S$ 不是不连通的,那么集合 $S$ 连通
  • 如果存在一个集合 $S_0\subsetneq S$ 是连通的,但是不存在任何一条有效的边 $e_(u,v)$,有 $u\in S_0~and~v\in \complement_SS_0$,那么 $S$ 是不连通的
  • 如果一条边的边权 $w_{e(u,v)}\leq t$,那么这一条边是有效的

方便起见,我们设函数 $T(S_0, S) $ 为存在于集合 $S_0$ 和 $\complement_SS_0$ 之间的边数,$P_S(t)$ 为当最大边权等于 $t$ 时,集合 $S$ 不连通的概率,从以上的定义出发,我们可以得到以下的方程:
$$
P_S(t)=\sum_{1\subset S_0\subsetneq S}(1-t)^{T(S_0,S)}[1-P_{S_0}(t)]
$$
$1$ 号点永远连通,$P_{\{1\}}(t)=0$

带入到最初的式子里面,得到:
$$
\begin{aligned}
E_S &= \int_0^1P_S(t)dt\\
&=\sum_{1\subset S_0\subsetneq S}\int_0^1(1-t)^{T(S_0,S)}[1-P_{S_0}(t)]dt\\
&=\sum_{1\subset S_0\subsetneq S}\left[\int_0^1(1-t)^{T(S_0,S)}dt-\int_0^1(1-t)^{T(S_0,S)}P_{S_0}(t)dt\right]\\
&=\sum_{1\subset S_0\subsetneq S}\left[\frac{1}{1+T(S_0,S)}-\int_0^1(1-t)^{T(S_0,S)}P_{S_0}(t)dt\right]\\
\end{aligned}
$$
现在,设 $DP$ 方程 :
$$
f[S][k]=\int_0^1(1-t)^kP_S(t)dt
$$
就可以得到转移:
$$
f[S][k] = \sum_{1\subset S_0\subsetneq S}\left[\frac{1}{1+T(S_0,S)}-f[S_0][k+T(S_0,S)]\right]
$$
所以最终答案便是$f[\{1,2,\cdots,n\}][0]$,边界条件$f[1][k]=0$,是不是很简单

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
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

inline int read(int u = 0, char c = getchar(), bool f = false) {
for (;!isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}

const int maxn = 10;

int Link[maxn];

int cnt[1 << maxn];

double f[1 << maxn][maxn * maxn];

int main() {
int n = read(), m = read();
for (int i = 1; i <= m; i++) {
int u = read() - 1, v = read() - 1;
Link[u] |= 1 << v;
Link[v] |= 1 << u;
}

for (register int i = 1; i < 1 << n; i++) cnt[i] = cnt[i >> 1] + (i & 1);

for (int i = 3; i < 1 << n; i++) if (i & 1) {
for (int j = i; j; j = (j - 1) & i) if (~j & 1) {
int t = 0;
for (int k = 0; k < n; k++) if ((i >> k) & (j >> k) & 1)
t += cnt[Link[k] & (i ^ j)];
for (int k = 0; k + t <= m; k++)
f[i][k] += 1.0 / (k + t + 1) - f[i ^ j][k + t];
}
}
printf("%.6lf", f[(1 << n) - 1][0]);
}