BZOJ3925 状压DP+概率DP

Author Avatar
WildRage 10月 30, 2017
  • 在其它设备中阅读本文章

转载自 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;
}

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