TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2266
  • 题目
  • P2266【HNOI2013 DAY2】游走
    限制 : 时间限制 : 20000 MS   空间限制 : 265536 KB  SPJ
    问题描述

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

    输入格式

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


    输入保证30%的数据满足N≤10,

    100%的数据满足2≤N≤500,  1<=M<=150000且是一个无向简单连通图。

    输出格式

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

    样例输入 1

    3 3 
    2 3
    1 2
    1 3

    样例输出 1

    3.333

    样例输入 2

    5 10
    1 2
    1 3
    1 4
    1 5
    2 3
    2 4
    2 5
    3 4
    3 5
    4 5

    样例输出 2

    17.800

    提示

    【样例1解释】
    边(1,2)编号为1,边(1,3)编号2,边(2,3)编号为3。