RainAir
My OI Blog
RainAir
「HNOI2009」最小圈
「HNOI2009」最小圈

题目描述

https://blog.aor.sd.cn/wp-content/uploads/2018/11/1486_1.jpg.gif

题目分析

典型的01分数规划题目。
用来处理求平均值最小类的问题。
我们根据简单的转换,可以得出答案ans是可以二分的。
二分一个答案ans,我们把每个边权都减掉ans,再跑最短路,如果找到了一个负权环,那么说明ans不是最优。

最后:提醒大家注意精度。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/157
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/f58587a8deed45cbb54a963eddaec349?s=80&d=mm&r=g

    及时总结,加强巩固,很好,加油 :niconiconit: :huaji: :niconiconi:

    5月前回复

RainAir

「HNOI2009」最小圈
题目描述 题目分析 典型的01分数规划题目。 用来处理求平均值最小类的问题。 我们根据简单的转换,可以得出答案ans是可以二分的。 二分一个答案ans,我们把每个边权都减掉ans,再跑…
扫描二维码继续阅读
2018-03-17
标签
近期评论