BZOJ3925 状压DP+概率DP

转载自 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#

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;
}