解题：luogu p4316 绿豆蛙的归宿----期望，拓扑排序

ydnhaha · 2018-09-04 21:55:53 · 个人记录

题面

建反图做拓扑排序，每次按题意用当前距离加边权除以指向点的出度更新答案。注意出度是没建反图之前的出度=。=

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int p[N],noww[2*N],goal[2*N],deg[N],ged[N];
double val[2*N],dis[N],t3;
int n,m,t1,t2,cnt;
queue<int> qs;
void link(int f,int t,double v)
{
    noww[++cnt]=p[f],p[f]=cnt;
    goal[cnt]=t,val[cnt]=v;
}
int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lf",&t1,&t2,&t3);
        link(t2,t1,t3),deg[t1]++,ged[t1]++;
    }
    qs.push(n);
    while(!qs.empty())
    {
        int tn=qs.front(); qs.pop();
        for(int i=p[tn];i;i=noww[i])
        {
            dis[goal[i]]+=(dis[tn]+val[i])/(double)ged[goal[i]];
            if(!(--deg[goal[i]]))
                qs.push(goal[i]);
        }
    }
    printf("%.2lf",dis[1]);
    return 0;
}