金牌导航中，如何运用高斯消元法解决Luogu P3232游走问题？

本文共计1704个文字，预计阅读时间需要7分钟。

这应用应是我们做的除模板外的第一道高端消元吧（是我的）+ 题目描述：+ 详细分析：+ 我们对编码的分配，非常明显可以发现以下的分配就是期望最小化的：+ 对过去的期望次数越大，边权越赋予期望越大

这应该是我们做的除模板外的第一道高斯消元吧（我是的） 题目描述：

详细分析：

我们对于编号的分配，很明显可以发现如下的分配就是期望最小的：对经过的期望次数越大的边赋予更小的编号。
那么问题就转化为了怎么求一条边的经过的期望次数，我们发现边数非常大所以肯定不好弄，所以我们就转而看很少的点。因为我们会发现如果我们能知道经过每个点的期望次数，那么这条边的期望次数很轻松就能表达出来。
比如如下的式子：（设 \(ans[i]\) 为经过第 \(i\) 个点的期望次数, \(du[i]\) 为第 \(i\) 个点的度数, \(res[i]\) 为经过第 \(i\) 条边的期望次数）

\[res[i] = \dfrac{ans[from]}{du[from]} + \dfrac{ans[to]}{du[to]} \]

这个式子应该很好理解，就是说每个点等概率地选择和他相连的边，所以选择这一条边地期望次数就是经过它的期望次数除以它的度数，也就是与他相连的边的数量，因为这条边可以从两个端点开始走然后经过，所以应该加上两个端点的值。
上文探讨了如果知道经过所有点的期望次数如何求经过这条边的期望，那么下文就来看看如何求经过每个点的期望次数。