题解 P4316 【绿豆蛙的归宿】

wangjyqh · 2018-08-27 20:22:42 · 题解

两种方法，正推和逆推

逆推：dp[i]表示从i到n的期望，方程的转移：对于一条从x到y边

dp[x]=\sum\limits_{i=1}^{oud[x]}(dp[y]+edge[i])/oud[x]

正推：dp[i]表示从1到i的期望，g[i]表示从1到i的概率，方程的转移：对于一条从x到y的边

dp[y]=\sum\limits_{i=1}^{ind[y]}(dp[x]+edge[i]\times g[x])/oud[x]

why?

逆推：

E(y)=p_1x_1+p_2x_2+\cdots\cdots+p_nx_n

E(x)=p_1(x_1+w)+p_2(x_2+w)+\cdots\cdots+p_n(x_n+w)=E(y)+\sum\limits_{i=1}^np_i\times w=E(y)+w

因为从i到n,所有概率和为1

正推：

E(x)=p_1x_1+p_2x_2+\cdots\cdots+p_nx_n

E(y)=p_1(x_1+w)+p_2(x_2+w)+\cdots\cdots+p_n(x_n+w)=E(x)+\sum\limits_{i=1}^np_i\times w\neq E(x)+w

因为从1到i，所有概率和i不为1

CODE（正推）:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXX=100010;
int oud[MAXX],ind[MAXX],ver[MAXX<<1],nxt[MAXX<<1],head[MAXX],edge[MAXX<<1];
double dp[MAXX],g[MAXX];
int tot,n,m;
inline void add(int x,int y,int z){
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
    oud[x]++;
    ind[y]++;
}
inline void topsort(){
    queue<int>q;
    for(int i=1;i<=n;++i)if(!ind[i])q.push(i);
    dp[1]=0.000;
    g[1]=1.000;
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            dp[y]+=(dp[x]*g[x]+(double)edge[i]*g[x])/(double)oud[x];
            g[y]+=g[x]/(double)oud[x];
            if(--ind[y]==0)q.push(y);
        } 
    }
}
int main(){
   cin>>n>>m;
   for(int i=1;i<=m;++i){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);
   }
   topsort();
   printf("%.2lf",dp[n]);
   return 0;
}

CODE2（逆推 )为了方便更新我们建了反图，但是出度以原图为准

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int MAXX=100010;
int head[MAXX],ver[MAXX<<1],nxt[MAXX<<1],edge[MAXX<<1],ind[MAXX],oud[MAXX];
int tot,n,m;
double dp[MAXX];
inline void add(int x,int y,int z){
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
}
inline void topsort(){
    queue<int>q;
    dp[n]=0;
    for(int i=1;i<=n;++i)if(!ind[i])q.push(i);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            dp[y]+=(dp[x]+(double)edge[i])/(double)oud[y];
            if(--ind[y]==0)q.push(y);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(y,x,z);
        ind[x]++;
        oud[x]++;
    }
    topsort();
    printf("%0.2lf",dp[1]);
    return 0;
}