bzoj3925

题意

给定一个n点m边的无向图,没有重边和自环,每条边的权值为[0,1]之间的随机变量。设S是使n个点连通的一个边集,求S中最大边的期望权值。

$n \leq 10, m \leq \frac{n(n-1)}{2}$

分析

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

证明稍后给出。

大致思路:

我们需要算的其实是:恰好选择k条边 使得图连通

恰好: 选k-1条边时不连通,选了第k条才连通。

那如何算呢?

设$con[S][i]$表示在集合$S$中选$i$条边,使得$S$连通的方案数。(不一定是恰好选$i$边连通)

$disc[S][i]$表示在集合$S$中选$i$条边,使得$S$不连通的方案数。

$edges[S]$表示集合$S$中的边数。

那么有关系:$con[S][i] + disc[S][i] = C(edges[S], i)$

重点来了: 如何计算恰好选$i$条边时连通呢?

$$ans[S][i] = con[S][i] - con[S][i-1]$$

那么$ans[S][i]$ 就是在集合$S$中选$i$条边,使得$S$恰好连通的方案数.

那么最终的答案就是

$$\sum \frac{ans[S][i]}{C(edges[S], i)} \times \frac{i}{m+1} $$


如何计算$con[S][i]$ ?

$con[S][i] = C(edges[S], i) - disc[S][i]$

如何计算$disc[S][i]$ ?

我们可以在集合$S$中找一个标志点$p$,那么$S$就可以分为两部分:一部分是包含$p$的集合$A$,另一部分是不包含$p$的集合$B$。

我们设包含$p$的集合是连通的,而另一个结合是无所谓的。

那么$$disc[S][j + k] = \sum con[A][j] \times C(edges[B], k)$$

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const double PI = acos(-1.0);
const int maxn = 1 << 11;
const int maxm = 46;
ll con[maxn][maxm], disc[maxn][maxm], edges[maxn], C[maxm][maxm];
int G[15][15];
void init() {
C[0][0] = 1;
for (int i = 1; i < maxm; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("2.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
init();
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0, u, v; i < m; i++) {
scanf("%d%d", &u, &v);
--u, --v;
G[u][v] = G[v][u] = 1;
}
int S = 1 << n;
for (int i = 0; i < S; i++)
for (int j = 0; j < n; j++)
if (i & (1 << j))
for (int k = j + 1; k < n; k++)
if (i & (1 << k)) edges[i] += G[j][k];
for (int i = 1, s; i < S; i++) {
if (__builtin_popcount(i) == 1) { // 集合里只有一个点
con[i][0] = 1;
continue;
}
s = i & (-i);
for (int sub = i & (i - 1); sub; sub = (sub - 1) & i)
if (sub & s)
for (int j = 0; j <= edges[sub]; j++)
for (int k = 0; k <= edges[i ^ sub]; k++)
disc[i][j + k] += con[sub][j] * C[edges[i ^ sub]][k];
for (int j = 0; j <= edges[i]; j++)
con[i][j] = C[edges[i]][j] - disc[i][j];
}
double ans = 0;
for (int i = 1; i <= m; i++)
ans += 1.0 * con[S - 1][i] / C[edges[S - 1]][i];
ans /= (m + 1);
ans = 1.0 * con[S - 1][m] / C[edges[S - 1]][m] - ans;
printf("%.6lf\n", ans);
}