一眼看去，这不是高斯消元吗？
然后发现数据范围是100000...
然后发现是DAG...直接拓扑序递推即可。
边(x, y，z)的贡献是P(x) * z / out[x]
#include <cstdio>
#include <queue>
const int N = ; struct Edge {
int v, nex, len;
}edge[N << ]; int top; int in[N], topo[N], e[N], n, out[N];
double p[N]; inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} inline void topo_sort() {
std::queue<int> Q;
for(int i = ; i <= n; i++) {
if(!in[i]) {
Q.push(i);
}
}
int t = ;
while(!Q.empty()) {
int x = Q.front();
Q.pop();
topo[++t] = x;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
in[y]--;
if(!in[y]) {
Q.push(y);
}
}
}
return;
} int main() {
int m;
scanf("%d%d", &n, &m);
for(int i = , x, y, z; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
in[y]++;
out[x]++;
}
topo_sort();
p[] = 1.0;
double ans = 0.0;
for(int a = ; a <= n; a++) {
int x = topo[a];
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
p[y] += p[x] / out[x];
ans += p[x] * edge[i].len / out[x];
}
}
printf("%.2lf", ans);
return ;
}
AC代码