题面
给一个图，边权为 ([0,1]) 的均匀分布的随机实数，求最小生成树的最大期望边权。
提示：对于 (n) 个 ([0,1]) 之间的随机变量 (x_1,x_2,dots,x_n) ，第 (k) 小的那个的期望值是(frac{k}{(n+1)})。
( ext{Solution:})
法一：期望 ( extbf{dp})
将题意写成数学公式，
在 (Kruscal) 的过程中求：
[E = sum_{i=1}^mfrac{i imes P(加入第i条边恰好连通)}{m+1}
]
其中 (frac{i}{m + 1}) 是期望边权，(P(加入第i条边恰好连通)) 是答案为第 (i) 大边的概率。
[egin{aligned}
E imes (m+1) &= sum_{i=1}^mi imes P(加入第i条边恰好连通)\
&=sum_{i=1}^mi imes (P(加入i条边使图连通)-P(加入i-1条边使原图连通))\
&=sum_{i=1}^mi imes (1-P(加入i条边使图不连通)-1+P(加入i-1条边使原图不连通))\
&=sum_{i=1}^mi imes (P(加入i-1条边使原图不连通) - P(加入i条边使图不连通))\
end{aligned}
]
展开，得：
[E imes (m+1) = sum_{i=0}^{m-1}P(加入i条边使图不连通) - m imes P(加入m条边使图不连通)
]
由于 (m imes P(加入m条边使图不连通) = 0) (题目保证连通)
[E imes (m+1) = sum_{i=0}^{m-1}P(加入i条边使图不连通)
]
设 (f[S][i]) 为 (G(S)) 中选 (i) 条边使原图不连通的方案数.
(g[S][i]) 为 (G(S)) 中选 (i) 条边使原图连通的方案数.
(ecnt[S]) 为 (G(S)) 中所包含的边数.
然后就可以转移了
首先显然有: (g[S][i] = C_{ecnt[S]}^{i} - f[S][i])
由于联通性的定义为任意两点可以到达，我们考虑钦定一个点（比如1），枚举它所能到的点集 (T) ,以及它不能到达的点集 (complement_{S}^T), 有转移:
[f[S][i] = sum_{Tsubsetneqq S} sum_{j=0}^{ecnt[T]} g[T][j] imes C_{ecnt[complement_{S}^T]}^{i-j}
]
然后就做完了。
code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO debug("GO
")
inline int rint() {
register int x = 0, f = 1; register char c;
while (!isdigit(c = getchar())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));
return x * f;
}
const int N = 12, M = 55;
int n, m;
LL graph[N], cnt[1 << N], ecnt[1 << N], f[1 << N][M], g[1 << N][M];
LL C[M][M];
void init() {
for (int i = 0; i <= m; ++ i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++ j)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("code.in", "r", stdin);
freopen("code.out", "w", stdout);
#endif
n = rint(), m = rint();
init();
for (int i = 0; i < m; ++ i) {
int u = rint(), v = rint(); u--, v--;
graph[u] |= (1 << v);
graph[v] |= (1 << u);
}
for (int i = 0; i < 1 << n; ++ i) {
for (int j = 0; j < n; ++ j)
if (i >> j & 1)
ecnt[i] += __builtin_popcount(graph[j] & i);
ecnt[i] >>= 1;//每条边算了两遍
}
for (int S = 0; S < 1 << n; ++ S)
if (S & 1){
if (__builtin_popcount(S) == 1) {
g[S][0] = 1;
continue;
}
for (int T = (S - 1) & S; T; T = (T - 1) & S)
if (T & 1) {
for (int i = 0; i <= ecnt[T] + ecnt[S ^ T]; ++ i) {
for (int j = 0; j <= min(ecnt[T], 1ll * i); ++ j)
f[S][i] += g[T][j] * C[ecnt[S ^ T]][i - j];
}
}
for (int i = 0; i <= ecnt[S]; ++ i)
g[S][i] = C[ecnt[S]][i] - f[S][i];
}
double ans = 0;
for (int i = 0; i < m; ++ i)
ans += 1.0 * f[(1 << n) - 1][i] / C[m][i];
printf("%.6lf
", ans / (m + 1));
}
法二：直接积分
设 (p(x)) 为答案为 (x) 的概率，由期望的定义：
[ans = int_0^1p(x)xdx
]
设 (F(x)) 为答案 (le x) 的概率，有：(F(a) = int_0^a p(x) dx)
考虑 (F(x)) 的意义：从小到大往图上加边，加入 (le x) 的边图联通的概率， 也就等于 1 - P( 加入 (le x) 的边原图不连通)。
令 (F(S,x)) 为加入 (le x)的边 (S) 联通的概率，有：
[F(S, x) =1 - sum_{S_osubsetneqq S}F(S_0, x)(1 - x)^{ecnt(S, S - S_0)}
]
由于钦定1为基准点，所以初始 (F(1) = 1) 。
这是一个关于 (x) 的多项式，而且可以 (dp) 求得，求导后得到 (p(x)) 再乘以 (x) 再积分出来，把 (1) 代进去减去 (0) 代进去就是答案了。
code
#include <iostream>
#include <cstring>
#include <vector>
#include <fstream>
typedef long long LL;
typedef unsigned long long uLL;
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define MP(x, y) std::make_pair(x, y)
#define DE(x) cerr << x << endl;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO cerr << "GO" << endl;
using namespace std;
inline void proc_status()
{
ifstream t("/proc/self/status");
cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}
inline int read()
{
register int x = 0; register int f = 1; register char c;
while (!isdigit(c = getchar())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c xor 48), isdigit(c = getchar()));
return x * f;
}
template<class T> inline void write(T x)
{
static char stk[30]; static int top = 0;
if (x < 0) { x = -x, putchar('-'); }
while (stk[++top] = x % 10 xor 48, x /= 10, x);
while (putchar(stk[top--]), top);
}
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
struct Poly
{
vector<LL> a;
Poly() { }
Poly(int n) { a.resize(n); }
int size() { return a.size(); }
LL& operator[](int x)
{ return a[x]; }
Poly operator * (Poly B) const
{
Poly ans(a.size() + B.size() - 1);
for (int i = 0; i < SZ(B); ++i)
for (int j = 0; j < SZ(a); ++j)
ans[i + j] += B[i] * a[j];
return ans;
}
Poly operator + (Poly B) const
{
Poly ans(max(SZ(B), SZ(a)));
for (int i = 0; i < SZ(ans); ++i)
{
if (i < SZ(a)) ans[i] += a[i];
if (i < SZ(B)) ans[i] += B[i];
}
return ans;
}
Poly operator - (Poly B) const
{
for (int i = 0; i < SZ(B); ++i)
B[i] = -B[i];
return (*this) + B;
}
} ;
Poly deriv(Poly a)
{
Poly b(SZ(a) - 1);
for (int i = 0; i < SZ(b); ++i)
b[i] = 1ll * (i + 1) * a[i + 1];
return b;
}
int n, m, E[12], ecnt[1 << 10 | 1][1 << 10 | 1];
Poly F[1 << 11 | 1], p, PW[202];
int main()
{
#ifndef ONLINE_JUDGE
freopen("xhc.in", "r", stdin);
freopen("xhc.out", "w", stdout);
#endif
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
E[u - 1] |= 1 << v - 1;
E[v - 1] |= 1 << u - 1;
}
for (int S = 1; S < 1 << n; ++S)
{
int bu = (~S) & ((1 << n) - 1);
for (int T = bu; T; T = (T - 1) & bu)
for (int i = 0; i < n; ++i)
if (S >> i & 1)
ecnt[S][T] += __builtin_popcount(E[i] & T);
}
PW[0].a.push_back(1);
PW[1].a.push_back(1), PW[1].a.push_back(-1);
for (int i = 2; i <= m; ++i)
PW[i] = PW[i - 1] * PW[1];
F[1].a.push_back(1);
for (int S = 2; S < 1 << n; ++S)
{
if (!(S & 1))
continue;
for (int T = (S - 1) & S; T; T = (T - 1) & S)
{
if (!(T & 1))
continue;
F[S] = F[S] - F[T] * PW[ecnt[T][S ^ T]];
}
F[S].a[0]++;
}
p = deriv(F[(1 << n) - 1]);
Poly mul(2);
mul[1] = 1;
p = p * mul;
LL res(0);
long double ans(0);
for (int i = 0; i < SZ(p); ++i)
ans += (long double) (p[i] % (i + 1)) / (i + 1), res += p[i] / (i + 1);
printf("%.6Lf
", ans + res);
return 0;
}