洛谷4316 绿豆蛙的归宿

Luogu

分析

设$f[i]$表示从$i$到$n$的期望路径长度。

设$u$有$k$条连向$v_1,v_2,...,v_k$,边权为$w_1,w_2,...,w_k$的路径,可以得到:

$f[u]=\frac{1}{k}\sum\limits_{i=1}^{k}(f[v_i]+w_i)$

显然$f[n]=0$,要求的是$f[1]$。

建反图,拓扑排序时顺便把期望求出来就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;
const int MAXM=200000+10;

struct Edge { int v,w,nxt; };
Edge e[MAXM];
int head[MAXN],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int n,m;
double ans[MAXN];
int degree[MAXN],out[MAXN];

queue<int> Q;
inline void solve() {
    Q.push(n);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            ans[v]+=(ans[u]+w)/degree[v];
            --out[v];
            if (!out[v]) Q.push(v);
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1,u,v,w;i<=m;++i) {
        u=read(),v=read(),w=read();
        addEdge(v,u,w);
        ++degree[u],++out[u];
    }
    solve(); printf("%.2f\n",ans[1]);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 39 PM

发表评论