题意

在一个无向图中，小$Z$以$1$为起点，每次以相等的概率选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小$Z$走到$N$（即终点），结束了这次游走，总得分为游走时经过的每一条边的编号之和。现在，请你对这$M$条边进行编号，使得小$Z$获得的总分的期望值最小。
输入保证:
1. $30$%的数据满足$N<=10$
2. $100$%的数据满足$2<=N<=500$且是一个无向简单连通图。

思路

首先要明白高斯消元

数学上，高斯消元法（或译：高斯消去法），是线性代数规划中的一个算法，可用来为线性方程组求解。但其算法十分复杂，不常用于加减消元法，求出矩阵的秩，以及求出可逆方阵的逆矩阵。不过，如果有过百万条等式时，这个算法会十分省时。一些极大的方程组通常会用迭代法以及花式消元来解决。当用于一个矩阵时，高斯消元法会产生出一个“行梯阵式”。高斯消元法可以用在电脑中来解决数千条等式及未知数。亦有一些方法特地用来解决一些有特别排列的系数的方程组。 ——转自百度百科

可以去过一过Luogu P3389 高斯消元的模板题
简单讲一下高斯消元。
如果有一个方程组，如：

将上面的方程转为下面的增广矩阵

接下来进行高斯消元。
首先找到一个第一列的数不为0的行（一般找第一列的数最大的行）（如果都为0就跳过当前步）
然后用它的第一列的数将下面行当前列的值化为0，变换过的初等矩阵与原矩阵等价，化为方程后依然成立
本矩阵第一列的数最大的为第三行就把第三行与第一行交换

然后下面行的当前列消去，如图

除了最后一列外，每一列都如此，最后得到上三角矩阵如图

这样我们就可以轻松求出$x1,x2,x3$了。
回归到这道题
我们设$deg_i$表示第$i$个点的度数，$f_i$表示第$i$个点期望经过次数：

由于当小$Z$到达$n$点时就停止游走了，因此不能考虑$n$点。接下来对$n−1$个$f_i$进行高斯消元求解。
设$g_i$表示第$i$条边期望经过次数：
$g_{i}=\frac{f_{u}}{d_{u}}+\frac{f_{v}}{d_{v}} \quad E_{i}=(u, v), u \neq n, v \neq n$
最后排序，贪心，因为要求期望值最小，那么就把最大的$g_i$编号标至最小，以此类推。

Code

高斯消元

游走

本文部分内容引自百度百科、bennettz、Siyuan。