正经题解

#include<cstdio>
#include<iostream>
using namespace std;
struct edge
{
int v,w,ne;
}
a[200010];
int n,m,tmp,top;
int in[100010],out[100010],h[100010],s[100010];
double f[200010],p[100010],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int x,y,z,i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[tmp]=(edge){y,z,h[x]};
h[x]=tmp;
out[x];
in[y]++;
}
s[++top]=1;
p[1]=1;
while(top > 0)//用一个栈维护所有可以选择的点
{
int x=s[top--];
for(int i=h[x];i!=0;i=a[i].ne)
{
in[a[i].v]--;
p[a[i].v]+=p[x]/out[x];//累加经过一个点的期望次数
f[i]=p[x]/out[x];//计算经过一个边的期望次数
if(in[a[i].v]==0)
{
s[top]=a[i].v;
}
}
}
for(int i=1;i<=m;i)
{
ans+=f[i]*a[i].w;
}
printf("%.2f\n",ans);
return 0;
}