P4316

· · 个人记录

绿豆蛙的归宿

就是个转移顺序的问题。

如果定义 f_x 表示起点到 x 的路径期望，那这题就会非常难做，因为边权的期望是要乘上概率的前缀乘的。

我们令 f_x 为 x 到终点的路径期望。

于是则有转移方程：

f_x=\sum_v\dfrac{f_v+wt_{x\rightarrow v}}{deg_x}

简单来说，就是邻边的期望直接算，后面路径本身的期望还要再乘上走到这条路径的概率，然后期望还要再相加。

记忆化搜索即可。

顺推下附。

一些详细的说明在 这里。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,u,v,w,tot,h;

ll ver[N*2+5],wt[N*2+5],nxt[N*2+5],head[N+5],deg[N+5];

bool vis[N+5];

double f[N+5];

double dp(ll p) {
    if(vis[p]) return f[p];vis[p]=1;
    for(ll i=head[p];i;i=nxt[i]) {
        f[p]+=dp(ver[i])/(double)deg[p]+(double)wt[i]/(double)deg[p];
    }
    return f[p];
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();w=read();
        add(u,v,w);deg[u]++;
    }

    printf("%.2f",dp(1));

    return 0;
}

代码（顺推拓扑）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,u,v,w,tot,h;

ll ver[N*2+5],wt[N*2+5],nxt[N*2+5],head[N+5],in_deg[N+5],out_deg[N+5];

double f[N+5],p[N+5];

queue<ll> q;

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();w=read();
        add(u,v,w);out_deg[u]++;in_deg[v]++;
    }

    q.push(1);p[1]=1;

    while(!q.empty()) {
        h=q.front();q.pop();
        for(ll i=head[h];i;i=nxt[i]) {
            if(--in_deg[ver[i]]==0) q.push(ver[i]);
            f[ver[i]]+=(f[h]+(double)wt[i]*p[h])/(double)out_deg[h];
            p[ver[i]]+=p[h]/(double)out_deg[h];
        }
    }

    printf("%.2f",f[n]);

    return 0;
}