Description：

给一个 $DAG$ ，在每个点走每条出边的概率是带权随机的，可以选择删掉一条边，问从一出发走到不能再走的最大期望步数。

$1\le n \le 10000,1\le m \le 100000$

Solution：

首先倒序拓扑 $DP$ 求出从每个点走到不能再走的期望长度 $f[i]$ ，那么对于一条边 $(u,v)$ 如果删掉他，那么受影响的一定是从 $1$ 到 $u$ 的路径上的点，考虑删掉这条边对全局答案的贡献，先考虑他对 $f[u]$ 的影响， $f[u]=\frac{\begin{align}\biggl( \sum_{\exist u\to v',v'\ne v}f[v']\times w(u,v')\biggr)+f[v]\times w(u,v)\end{align}}{\begin{align}\sum_{\exist u\to v',v'\ne v}w(u,v')+w(u,v)\end{align}}$ ，删掉他之后 $f[u]=\frac{\begin{align}\sum_{\exist u\to v',v'\ne v}f[v']\times w(u,v')\end{align}}{\begin{align}\sum_{\exist u\to v',v'\ne v}w(u,v'))\end{align}}$ ，这两项作差就是对 $f[u]$ 的影响，考虑对 $f[u]$ 的影响有多大概率会影响全局答案，不难发现这个概率就是从 $1$ 走到 $u$ 的概率，也就是删边会产生影响的概率，于是做差乘以概率再加上原答案就是删掉这条边之后的期望。

感觉很多期望问题考虑对全局期望的影响就可以方便计算概率了，因为全局概率一般都比较好算，也好理解，因为考虑当前情况的话就比较复杂。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10010

#define MAXM 100010

int sum[MAXN];

struct edges

{

	int fr,to,w;

}e[MAXM];

struct edgetable

{

	struct edge

	{

		int to,nxt,v;

	}e[MAXM];

	int edgenum;

	int lin[MAXN];

	int ind[MAXN],deg[MAXN];

	edgetable(){memset(lin,0,sizeof(lin));memset(ind,0,sizeof(ind));edgenum = 0;}

	void add(int a,int b,int c)

	{

		++deg[a];++ind[b];

		++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

		return;

	}

}e1,e2;

double p[MAXN],f[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		++a;++b;sum[a] += c;

		e[i].fr = a;e[i].to = b;e[i].w = c;

		e1.add(a,b,c);e2.add(b,a,c);

	}

	queue<int> q;

	p[1] = 1.0;

	for(int i = 1;i <= n;++i)

		if(e1.ind[i] == 0)

			q.push(i);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = e1.lin[k];i != 0;i = e1.e[i].nxt)

		{

			p[e1.e[i].to] += p[k] * ((double)e1.e[i].v / sum[k]);

			--e1.ind[e1.e[i].to];

			if(e1.ind[e1.e[i].to] == 0)

				q.push(e1.e[i].to);

		}

	}

	for(int i = 1;i <= n;++i)

		if(e2.ind[i] == 0)

			q.push(i);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = e2.lin[k];i != 0;i = e2.e[i].nxt)

		{

			f[e2.e[i].to] += (f[k] + 1.0) * ((double)e2.e[i].v / sum[e2.e[i].to]);

			--e2.ind[e2.e[i].to];

			if(e2.ind[e2.e[i].to] == 0)

				q.push(e2.e[i].to);

		}

	}

	double ans = f[1];

	for(int i = 1;i <= m;++i)

	{

		int u = e[i].fr,v = e[i].to,w = e[i].w;

		double del = (f[u] * sum[u] - (f[v] + 1.0) * w) / (sum[u] - w) - f[u];

		ans = max(ans,f[1] + del * p[u]);

	}

	printf("%.6lf\n",ans);

	return 0;

}