刷水反被水题日，拓扑写炸WA了2发T T...
因为是DAG图，可以直接递推，不需要高斯消元
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=500010,inf=1e9; struct poi{int too,dis,pre;}e[maxn]; int n,m,x,y,z,top,cnt,tot; int ru[maxn],chu[maxn],st[maxn],num[maxn],last[maxn]; double E[maxn]; inline void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } inline void add(int x,int y,int z){e[++tot].too=y;e[tot].dis=z;e[tot].pre=last[x];last[x]=tot;} void topsort() { for(int i=1;i<=n;i++)if(!ru[i])st[++top]=i,num[++cnt]=i; while(top) { int now=st[top--]; for(int i=last[now];i;i=e[i].pre) { ru[e[i].too]--; if(!ru[e[i].too])st[++top]=e[i].too,num[++cnt]=e[i].too; } } } int main() { read(n);read(m); for(int i=1;i<=m;i++)read(x),read(y),read(z),add(x,y,z),chu[x]++,ru[y]++; topsort(); for(int i=cnt;i;i--) for(int j=last[num[i]];j;j=e[j].pre) E[num[i]]+=(E[e[j].too]+e[j].dis)*1.0/chu[num[i]]; printf("%.2lf ",E[1]); }