P3199 [HNOI2009]最小圈

    • 276通过
    • 614提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 SPFA 分数规划 深度优先搜索,DFS 2009 湖南
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    考虑带权的有向图 $G=(V,E)$ 以及 $w:E\rightarrow R$ ,每条边 $e=(i,j)(i\neq j,i\in V,j\in V)$ 的权值定义为 $w_{i,j}$ ,令 $n=|V|$ 。 $c=(c_1,c_2,\cdots,c_k)(c_i\in V)$ 是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})(1\le i<k)$ 和 $(c_k,c_1)$ 都在 $E$ 中,这时称 $k$ 为圈 $c$ 的长度同时令 $c_{k+1}=c_1$ ,并定义圈 $c=(c_1,c_2,\cdots,c_k)$ 的平均值为 $\mu(c)=\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}/k$ ,即 $c$ 上所有边的权值的平均值。令 $\mu'(c)=Min(\mu(c))$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。现在的目标是:在给定了一个图 $G=(V,E)$ 以及 $w:E\rightarrow R$ 之后,请求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\mu'(c)=Min(\mu(c))$

    输入输出格式

    输入格式:

    第一行2个正整数,分别为 $n$ 和 $m$ ,并用一个空格隔开,只用 $n=|V|,m=|E|$ 分别表示图中有 $n$ 个点 $m$ 条边。 接下来m行,每行3个数 $i,j,w_{i,j}$ ,表示有一条边 $(i,j)$ 且该边的权值为 $w_{i,j}$ 。输入数据保证图 $G=(V,E)$ 连通,存在圈且有一个点能到达其他所有点。

    输出格式:

    请输出一个实数 $\mu'(c)=Min(\mu(c))$ ,要求输出到小数点后8位。

    输入输出样例

    输入样例#1: 复制
    4 5
    1 2 5
    2 3 5
    3 1 5
    2 4 3
    4 1 3
    输出样例#1: 复制
    3.66666667
    输入样例#2: 复制
    2 2
    1 2 -2.9
    2 1 -3.1
    输出样例#2: 复制
    -3.00000000

    说明

    对于100%的数据, $n\le 3000,m\le 10000,|w_{i,j}| \le 10^7$

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