NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  7. 7. 题解前的扯淡
  8. 8. 题解

转载自 Cooook
BZOJ3925 状压DP+概率DP
转载请注明原文地址

Description

傲娇少女幽香是一个很萌很萌的妹子,而且她非常非常地有爱心,很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不,幻想乡突然发生了地震,所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有n个地方,那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的,一共有m条边。现在这m条边由于地震的关系,全部都毁坏掉了。每条边都有一个修复它需要花费的时间,第i条边所需要的时间为ei。地震发生以后,由于幽香是一位人生经验丰富,见得多了的长者,她根据以前的经验,知道每次地震以后,每个ei会是一个0到1之间均匀分布的随机实数。并且所有ei都是完全独立的。 现在幽香要出发去帮忙修复道路了,她可以使用一个神奇的大魔法,能够选择需要的那n-1条边,同时开始修复,那么修复完成的时间就是这n-1条边的ei的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边ei的值,然后再选择完成时间最小的方案。 幽香在走之前,她想知道修复完成的时间的期望是多少呢?

Input

第一行两个数n,m,表示地方的数量和边的数量。其中点从1到n标号。
接下来m行,每行两个数a,b,表示点a和点b之间原来有一条边。
这个图不会有重边和自环。

Output

一行输出答案,四舍五入保留6位小数。

Sample Input

1
2
3
4
5
5 4
1 2
1 5
4 3
5 3

Sample Output

1
0.800000

HINT

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

题解前的扯淡

贼NB的一道题,有两种做法,PoPoQQQ大爷的积分没看懂…于是写了概率DP
WQ刚了一天没刚出来,ZZH还在刚…
听WQ说dg说这种题刚不出来就弃了吧233333

题解

题目让求的是最小生成树最大边的期望
我们设最小生成树的最大边的排名为$i$
设$F(i)$ 为最小生成树最大边排名为$i$的贡献
由提示可知$F(i) = \frac{i}{m+1}$
设$P(i)$为最小生成树最大边排名为$i$的概率
则$Ans=\sum_{i=1}^{m}{\frac{i*P(i)}{m+1}}$
然后就可以惊喜的发现这个$P(i)$并不好求
考虑转化
设$T(i)$为最小生成树最大边排名大于等于$i$的概率
那么$Ans=\frac{\sum_{i=1}^{m}{T(i)}}{m+1}$
至于为什么
首先根据定义$T(i)=\sum_{j=i}^{m}{P(j)}$
那么每个$P(i)$被累加的次数正好是$i$次
所以成立
但$T(i)$还是不好求
而最小生成树最大边的排名为$i$则说明排名小于$i$的边不能使图联通
设$M(i)$为排名小于i的边不能使图联通的概率
所以$T(i)=M(i)$
所以求$\frac{\sum_{i=0}^{m}{M(i)}}{m+1}$就是答案了
然后怎么还是不好求…
不联通的不好求,联通的还不好求么
终于进入$DP$的环节了….
由于$n$的范围很小,所以我们考虑状态压缩
设$f_{i,j}$为点集为$i$有j条边且点之间不联通的方案数
设$g_{i,j}$为点集为$i$有j条边且点之间联通的方案数
设$cnt_i$为点集为$i$的边的数量
从$cnt_i$条边里选$j$条边的方案数为$C_{cnt_i}^{j}$
而选出来$j$条边后这个点集只有联通和不联通两种状态
所以$f_{i,j}+g_{i,j}=C_{cnt_i}^{j}$
方程的转移可以通过选取这个联通块内的一个点,然后枚举那些点和这个点联通来转移
即为$f_{i,j}+=g_{S,k}*C_{cnt_{i-S}}^{j-k}$
然后根据$f_{i,j}+g_{i,j}=C_{cnt_i}^{j}$来转移$g$
最后统计答案的时候$\frac{\sum_{i=0}^{m}{\frac{f_{ALL,i}}{C_m^i}}}{m+1}$
终于完了QWQ….

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
#include <stdio.h>
#include <iostream>
#define int long long
#define fi first
#define se second
#define lowbit(_) ((_)&(-_))
typedef std::pair<int,int> pii;
int f[1<<10][50],g[1<<10][50],n,m,full,cnt[1<<10],C[50][50];
pii a[50];


char xb[1<<15],*xs,*xt;
#define getc() (xs == xt && (xt = (xs = xb) + fread(xb,1,1<<15,stdin),xs == xt)?0:*xs++)
inline int read() {
int x = 0, f = 1;
char ch = getc();
for (; ch < '0' || ch > '9'; ch = getc()) if (ch == '-') f = -f;
for (; ch >= '0' && ch <= '9'; ch = getc()) x = x * 10 + (ch ^ 48);
return x * f;
}

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

inline int Cnt_Bit(int S) {
int cnt = 0;
for (; S; S -= lowbit(S)) cnt ++;
return cnt;
}

signed main() {
Pre_Work();
n = read(); m = read(); full = (1 << n) - 1;
for (int i = 1; i <= m; i++) a[i].fi = read(),a[i].se = read();
for (int i = 1; i <= full; i++)
for (int j = 1; j <= m; j++)
if (((1<<a[j].fi-1) & i) && ((1<<a[j].se-1) & i)) cnt[i] ++;
for (int i = 1; i <= full; i++) {
if (Cnt_Bit(i) == 1) {
g[i][0] = 1;
continue;
}
int j = lowbit(i);
for (int S = (i - 1) & i; S; S = (S - 1) & i)
if (j & S) {
for (int k = 0; k <= cnt[S]; k++)
for (int o = 0; o <= cnt[i ^ S]; o++)
f[i][o+k] += g[S][k] * C[cnt[i^S]][o];
}
for (int k = 0; k <= cnt[i]; k++) g[i][k] = C[cnt[i]][k] - f[i][k];
}
double Ans = 0.0;
for (int i = 0; i <= m; i++) Ans += f[full][i] / 1.0 / C[cnt[full]][i];
printf("%.6lf\n",Ans/(m+1));
return 0;
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2017/10/30/119/

本文最后更新于 天前,文中所描述的信息可能已发生改变