BZOJ 3036: 绿豆蛙的归宿

定义 \(f_u\) 为 \(u \to n\) 的期望长度
拓扑排序之后得到拓扑序从后往前dp
\(f_u = \sum \limits_{(u,v) \in E}\dfrac{f_v + cost_{u,v}}{Outdeg_u}\)

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define db double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define Edg int cnt=1,head[N],to[N*2],ne[N*2];void addd(int u,int v){to[++cnt]=v;ne[cnt]=head[u];head[u]=cnt;}void add(int u,int v){addd(u,v);addd(v,u);}
#define Edgc int cnt=1,head[N],to[N*2],ne[N*2],c[N*2];void addd(int u,int v,int w){to[++cnt]=v;ne[cnt]=head[u];c[cnt]=w;head[u]=cnt;}void add(int u,int v,int w){addd(u,v,w);addd(v,u,w);}
#define es(u,i,v) for(int i=head[u],v=to[i];i;i=ne[i],v=to[i])
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline char getc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline int _() {
    int x = 0, f = 1; char ch = getc();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getc(); }
    while (ch >= '0' && ch <= '9') { x = x * 10ll + ch - 48; ch = getc(); }
    return x * f;
}
const int N = 4e5 + 7;
Edgc
int n, m, in[N], out[N], que[N];
db f[N];

int main() {
    n = _(), m = _();
    rep(i,0,m) {
        int u = _() - 1, v = _() - 1, w = _();
        addd(u, v, w);
        out[u]++, in[v]++;
    }
    int l = 0, r = 0;
    que[r++] = 0;
    while (r - l >= 1) {
        int u = que[l++];
        es(u,i,v) {
            if (!--in[v]) que[r++] = v;
        }
    }
    f[n - 1] = 0;
    per(i,0,n-1) {
        int u = que[i];
        f[u] = 0;
        es(u,j,v){
            int w = c[j];
            f[u] += (f[v] + w) / out[u];
        }
    }
    printf("%.2f\n", f[0]);
    return 0;
}

BZOJ 3036: 绿豆蛙的归宿

原文：https://www.cnblogs.com/Mrzdtz220/p/12332611.html