P3199 [HNOI2009]最小圈

    • 164通过
    • 379提交
  • 题目提供者 洛谷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类违反进行处理。