题目描述
给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。
小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。
输入格式
第一行是两个整数，分别表示该图的顶点数 $n$ 和边数 $m$。
接下来 $m$ 行每行两个整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。
输出格式
输出一行一个实数表示答案，保留三位小数。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
说明/提示
样例输入输出 1 解释
边 $(1,2)$ 编号为 $1$，边 $(1,3)$ 编号 $2$，边 $(2,3)$ 编号为 $3$。
数据规模与约定
- 对于 $30%$ 的数据，保证 $n\leq 10$。
- 对于 $100%$ 的数据，保证 $2\leq n \leq 500$， $1 \leq m \leq 125000$，$1 \leq u, v \leq n$，给出的图无重边和自环，且从 $1$ 出发可以到达所有的节点。
题解
我们希望统计经过每条边的期望次数，显然经过次数越多的点分配越小的编号是合理的。
但边的数目上限可能是 $n^2$ 级别，我们先统计经过每个点的期望次数。
我们设 $deg_i$ 表示第 $i$ 个点的度数，$f(i)$ 表示第 $i$ 个点期望经过次数：
$$ f(i) = \begin{cases} \sum_{(i,j) \in E, j \neq n} \frac{f_j}{deg_j} + 1 & i = 1 \ \sum_{(i,j) \in E, j \neq n} \frac{f_j}{deg_j} & 1 < i < n \end{cases} $$
接下来我们对 $n - 1$ 个 $f(i)$ 进行高斯消元求解。
我们设 $g(u,v)$ 表示第 $i$ 条边 $(u,v)$ 期望经过次数：
$$ g(u,v) = \frac{f(u)}{d_u} + \frac{f(v)}{d_v} \quad u \neq n, v \neq n $$
有了每条边的经过次数期望，为期望越小的边分配越大的编号即可。
时间复杂度：$O(n^3)$。
