A6104 | $「HNOI2013」游走$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入第一行是正整数 $N$ 和 $M$ ，分别表示该图的顶点数和边数，接下来 $M$ 行每行是整数 $u , v$ ( $1 \le u,v \le N$ )，表示顶点 $u$ 与顶点 $v$ 之间存在一条边。

输出仅包含一个实数，表示最小的期望值，保留 3 位小数。

输入 #1

输出 #1

3.333

C++ 编辑器

输入

输出