给一个 nn 个点,mm 条边的图,边权为 [0,1][0, 1] 的均匀分布的随机实数,求最小生成树的最大边权的期望

提示：对于 nn 个 [0,1][0, 1] 之间的随机变量 ，第 kk 小的那个的期望值是kn+1\frac{k}{n + 1}

n≤10,m≤n(n−1)2n\le 10, m\le \frac{n(n-1)}{2}

LOJ2136

Solution

19-9-4-1

设 f[S][i]f[S][i] 为 G(S)G(S) 中选 ii 条边使原图不连通的方案数, g[S][i]g[S][i] 为 G(S)G(S) 中选 ii 条边使原图连通的方案数, ecnt[S]ecnt[S] 为 G(S)G(S) 中所包含的边数.

首先显然有: g[S][i]=(ecnt[S]i)−f[S][i]g[S][i] = {ecnt[S] \choose i}- f[S][i] ，由于联通性的定义为任意两点可以到达，我们考虑钦定一个点，枚举它所能到的点集 TT, 以及它不能到达的点集 ∁ST\complement_{S}^T, 有转移:

f[S][i]=∑T⫋S∑j=0min{i,ecnt[T]}g[T][j]×(ecnt[∁ST]i−j) f[S][i] = \sum_{T\subsetneqq S} \sum_{j=0}^{\min\{i, ecnt[T]\}} g[T][j] \times {ecnt[\complement_{S}^T]\choose i - j}

Summary

前面期望转概率的部分有点巧妙

后半部分又是这种钦定某一个点的计数方法，一定要掌握

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
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 10 + 5, Maxs = (1 << 10) + 10, Maxm = 50 + 10;

namespace MATH
{
	LL C[Maxm][Maxm];

	inline void init (int n = 45)
	{
		C[0][0] = 1;
		for (int i = 1; i <= n; ++i)
		{
			C[i][0] = 1;
			for (int j = 1; j <= i; ++j)
				C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
		}
	}
}

using namespace MATH;

int N, M, ALL;
int A[Maxn][Maxn];
int ecnt[Maxs];

inline void print (int x)
{
	int buc[30]; buc[0] = 0;
	while (x) buc[++buc[0]] = x & 1, x >>= 1;
	for (int i = 1; i <= buc[0]; ++i) cout << buc[i];
	for (int i = buc[0] + 1; i <= N; ++i) cout << 0;
}

inline void Init ()
{
	ALL = (1 << N) - 1;

	for (int S = 0; S <= ALL; ++S)
	{
		for (int i = 1; i <= N; ++i)
		{
			if (S & (1 << (i - 1))) continue;
			int T = S | (1 << (i - 1));
			ecnt[T] = ecnt[S];
			for (int j = 1; j <= N; ++j)
				if (S & (1 << (j - 1)))
					ecnt[T] += A[i][j];
		}
	}
}

LL f[Maxs][Maxm], g[Maxs][Maxm];

inline void Solve () // f : 不联通， g : 联通
{
	Init ();

	for (int S = 0; S <= ALL; ++S)
	{
		if (__builtin_popcount (S) == 1) f[S][0] = 0, g[S][0] = 1;

		int pos = 0;
		for (int j = 0; j < N; ++j) if (S & (1 << j)) pos = 1 << j;

		for (int i = 0; i <= ecnt[S]; ++i)
		{
			g[S][i] = C[ecnt[S]][i];
			for (int T = (S - 1) & S; T > 0; T = (T - 1) & S)
			{
				if (!(T & pos)) continue;
				for (int j = 0; j <= min (i, ecnt[T]); ++j)
					f[S][i] += g[T][j] * C[ecnt[S ^ T]][i - j];
			}
			g[S][i] -= f[S][i];
		}
	}

	double ans = 0;
	for (int i = 0; i < M; ++i) ans += 1.0 * f[ALL][i] / C[M][i];

	printf("%.6lf\n", ans / (M + 1));
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>();
		A[x][y] = A[y][x] = 1;
	}
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	MATH :: init ();
	Input ();
	Solve ();

	return 0;
}