洛谷$P4316$ 绿豆蛙的归宿期望

佚名 6年前 (2019-05-04) 随笔 1461人围观抢沙发百度已收录

正解:期望

解题报告:

传送门!

看懂题目还是挺水的$(bushi$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

三个方法,但因为题目太水了懒得一一介绍了,,,反正都是期望,,,$so$随便港个最简单的趴$QwQ$

直接考虑每条边的贡献,就会是概率*长度

概率按拓扑序求(当然如果直接求个概率而已的话可以直接用dfs来着,,,

然后就做完辽,,,?

$maya$我做的题越来越水辽,,,/流泪

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define int long long
#define lf long double
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=100000+10;
int n,m,head[N],out[N],ed_cnt,in[N];
lf f[N],as;
bool vis[N];
struct ed{int to,nxt,wei;}edge[N<<4];
queue<int>Q;

il int read()
{
    ri x=0;rb y=1;rc ch=gc;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il void ad(ri x,ri y,ri z){edge[++ed_cnt]=(ed){y,head[x],z};head[x]=ed_cnt;}
il void topsort()
{
    rp(i,1,n)if(!in[i])Q.push(i);
    while(!Q.empty())
    {
        int nw=Q.front();Q.pop();
        e(i,nw)
        {
            f[t(i)]+=(lf)f[nw]/out[nw];as+=(lf)f[nw]/out[nw]*w(i);
            --in[t(i)];if(!in[t(i)])Q.push(t(i));
        }
    }
}

signed main()
{
    freopen("4316.in","r",stdin);freopen("4316.out","w",stdout);
    n=read();m=read();rp(i,1,m){ri x=read(),y=read(),z=read();ad(x,y,z);++in[y];++out[x];}
    f[1]=1;topsort();printf("%.2Lf\n",as);
    return 0;
}