【Luogu】P3343地震后的幻想乡（对积分概率进行DP）

　　题目链接

　　神难qwq。配合rqy的博客食用。

　　首先我们学到有一个概率函数$p(x)$表示某事件发生概率取值小于x的函数。这个函数有什么特点呢？

　　那就是$\int_{-∞}^{∞}p(x)dx=1$

　　这个是显然的

　　然后我们令p(x)为首次联通的时间的概率分布函数

　　这其实等价于生成树的最大权边等于x的概率，对不对（我虚啊，我很可能理解错的）

　　然后呢，就有一个期望的式子

　　$EX=\int tp(t)dt$

　　我忘了是为什么了（上午rqy才刚给我讲过，现在就忘了），我太菜了。

　　然后本题中，期望就是$EX=\int_{0}^{1}xp(x)dx$

　　$=\int_{0}^{1}p(x)( \int_{0}^{x}1ds)dx$

　　$=\int_{0}^{1}(\int_{s}^{1}p(x)dx)ds$

　　然后我们把括号里面那个玩意设成P(s)好了

　　所以原式被我们化成了$\int_{0}^{1}P(s)ds$

　　然后……emm等一会我忘了我要干嘛了qwq

　　……
　　然后我们设一个$f_{x,S}$表示集合S（S包含1节点）在x时刻前不连通，x时刻恰好联通的概率

　　因为在x时刻不连通，所以我们考虑它的转移

　　$f_{x,S}=\sum\limits_{1属于S'}^{S'包含于S}(1-f_{x,S'})(1-x)^{T(S',S-S')}$

　　这什么意思呢？

　　我们设T(A,B)为A点集和B点集之间的边数。

　　首先我们看见里面有一个$(1-f_{x,S'})$，这个玩意的意思是

　　既然我们的S集合要恰好联通，那在这之前S'作为S的一个子集是一定要联通的。而f表示的是不连通的概率，所以就是1-x呗。

　　而且S'和外界不要联通。

　　既然S和外界不要联通，那每条边在x时刻不连通的概率是(1-x)，那T条边都不连通的概率就是$(1-x)^{T(S',S-S')}$

　　所以说$f_{x,S'}$就是这么一个玩意儿。

　　然后我们把x当成参，就有了$f_{S'}(x)$这么一个东西。

　　然后……比如说有个全集U

　　最后我们求的就是这么一个玩意

　　$\int_{0}^{1}f_{U}(x)dx$

　　然后下面的我就全忘了，顺着rqy的笔迹讲，不过我自己也看不懂是在干嘛qwq

　　我们设$dp_{S,k}=\int_{0}^{1}f_{S}(x)(1-x)^{k}dx$

　　$=\int_{0}^{1}(\sum\limits_{1属于S'}^{S'包含于S}(1-f_{S'}(x))(1-x)^{T(S',S-S')})(1-x)^{k}dx$

　　设t=T(S',S-S')

　　$dp_{S,k}=\sum\limits_{1属于S'}^{S'包含于S}\int_{0}^{1}(1-f_{S'}(x))(1-x)^{t+k}dx$

　　$=\sum\limits_{1属于S'}^{S'包含于S}\int_{0}^{1}(1-x)^{t+k}-f_{S'}(x)(1-x)^{t+k}dx$

　　我们发现后面那个玩意等于$dp_{S',t+k}$

　　就可以搞啦。至于k到底干嘛的，rqy说不表示实际意义，只是用来简化计算，我没听懂。qwq

　　最后求的答案就是$dp_{U,0}$

　　然后就是递归搞一搞DP输出。

　　（当然到考场上如果碰到这道题我倾向于手玩。智商-INFqwq。）

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cstdlib>

#define maxn 11

#define maxm 55

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

double f[<<maxn][maxm];

int q[<<maxn][<<maxn];

bool vis[<<maxn][maxm];

double dfs(int state,int t){

    if(state==)    return ;

    if(vis[state][t])    return f[state][t];

    vis[state][t]=;

    double &ans=(f[state][t]=.);

    for(int sta=(state-)&state;sta!=state;sta=(sta-)&state)

        if(sta&){

            ans+=1.0/(t+q[sta][state&(~sta)]+);

            ans-=dfs(sta,t+q[sta][state&(~sta)]);

        }

    return ans;

}

int main(){

    int n=read(),m=read();

    int Max=<<n;

    for(int i=;i<=m;++i){

        int a=read(),b=read();

        a--;b--;

        for(int sta=;sta<Max;++sta){

            if(((sta>>a)&)==)    continue;

            for(int stb=;stb<Max;++stb){

                if(((stb>>b)&)==)    continue;

                q[sta][stb]++;    q[stb][sta]++;

            }

        }

    }

    printf("%.6lf",dfs(Max-,));

    return ;

}

巴特西

【Luogu】P3343地震后的幻想乡（对积分概率进行DP）

最新文章

热门文章