P3232 [HNOI2013] 游走

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图，顶点从 $1$ 编号到 $n$，边从 $1$ 编号到 $m$。

小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 $n$ 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $m$ 条边进行编号，使得小 Z 获得的总分的期望值最小。

输入格式

第一行是两个整数，分别表示该图的顶点数 $n$ 和边数 $m$。

接下来 $m$ 行每行两个整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。

输出格式

输出一行一个实数表示答案，保留三位小数。

输入输出样例 #1

输入 #1

3 3
2 3
1 2
1 3

输出 #1

3.333

说明/提示

样例输入输出 1 解释

边 $(1,2)$ 编号为 $1$，边 $(1,3)$ 编号 $2$，边 $(2,3)$ 编号为 $3$。

数据规模与约定

• 对于 $30\mathrm{\%}$ 的数据，保证 $n\le 10$。
• 对于 $100\mathrm{\%}$ 的数据，保证 $2\le n\le 500$， $1\le m\le 125000$，$1\le u,v\le n$，给出的图无重边和自环，且从 $1$ 出发可以到达所有的节点。

题解

我们希望统计经过每条边的期望次数，显然经过次数越多的点分配越小的编号是合理的。

但边的数目上限可能是 $n^2$ 级别，我们先统计经过每个点的期望次数。

我们设 $de{g}_i$ 表示第 $i$ 个点的度数，$f(i)$ 表示第 $i$ 个点期望经过次数：

$$f(i)=\{\begin{array}{ll}\sum _{(i,j)\in E,j\ne n}\frac{f_j}{de{g}_j}+1& i=1\\ \sum _{(i,j)\in E,j\ne n}\frac{f_j}{de{g}_j}& 1<i<n\end{array}$$

接下来我们对 $n-1$ 个 $f(i)$ 进行高斯消元求解。

我们设 $g(u,v)$ 表示第 $i$ 条边 $(u,v)$ 期望经过次数：

$$g(u,v)=\frac{f(u)}{d_u}+\frac{f(v)}{d_v}u\ne n,v\ne n$$

有了每条边的经过次数期望，为期望越小的边分配越大的编号即可。

时间复杂度：$O(n^3)$。