[文章目录]
Description
给出一个有向无环的连通图,起点为1终点为N,每条边都有一个长度。绿豆蛙从起点出发,走向终点。到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?N<=100000,M<=2*N
被自己蠢哭,循环边又写成了n。dp[i]表示第i个点到n的期望复杂度。然后拓扑转移就好了。(dfs好像也行)
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int head[110000],to[210000],nxt[210000],data[210000],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
data[cnt]=z;
}
int cd[110000],chu[110000];
double dp[110000];
void topsort()
{
queue<int>q;
for(int i=1;i<=n;i++)
if(!cd[i]) q.push(i);
int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
{
dp[to[i]]+=(dp[x]+data[i])*1.0/chu[to[i]];
cd[to[i]]--;
if(!cd[to[i]]) q.push(to[i]);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
cd[x]++; add(y,x,z);
}
for(int i=1;i<=n;i++) chu[i]=cd[i];
topsort();
printf("%.2lf\n",dp[1]);
return 0;
}