P3232 [HNOI2013]游走

    • 733通过
    • 1.9K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 期望 高斯消元 2013 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一个无向连通图,顶点从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且是一个无向简单连通图。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    3 3
    2 3
    1 2
    1 3
    输出样例#1: 复制
    3.333

    说明

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。