转载自 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
5 4
1 2
1 5
4 3
5 3
Sample Output
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….
#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;
}