来源和评测点
USACO 2005 March Gold
Bzoj1738
Poj2391
Caioj1118
题目
【题目大意】
下雨了,有F(1<=F<=200)个牛棚,这F个牛棚之间有P(1<=P<=1500)条无向边(有耗时)
每个牛棚有两个值A和B(A表示一开始这个牛棚有A头牛,B表示下雨时该牛棚最多可以容纳B头牛躲雨)。
问最少需要提前多少时间响“下雨警告”才能让所有牛在下雨前都能够找到可以遮雨的地方。
重点句:
The paths are wide,so that any number of cows can traverse a path in either direction. 无向边
Fields are small compared to the paths and require no time for cows to traverse. 将牛棚看作点
【输入格式】
两个整数: F 和 P
接下来F行,第i行两个整数A和B(A、B的范围都是:0..1000)描述第i个牛棚
接下来P行,每行三个整数。X Y L,表示牛棚X和牛棚Y之间有一条边,耗时是L(1<=L<=1,000,000,000)
【输出格式】
输出一行,即为最短的时间,如果无法使得所有牛都能够有地方避雨,那么输出 “-1”
【输入样例】
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
【输出样例】
110
【样例解释】
牛棚1安排4头牛到牛棚2,牛棚1再安排1头牛走到牛棚2,再走到牛棚3避雨。
分析
网络流教程和题目分类参见:
【OI之路】03图论算法-4网络流
其他网络流题目参见:Tag-网络流
本题入选了好题:Tag-好题
这道题建议大家像我一样仔细想想,
别急着看题解,虽然你到我这个页面很可能是来膜题解的
由于边比较复杂,但又是无向图
考虑Floyd获得两点之间最短耗时
然后两点之间只存在一条边了
原问题转化成:
选一些边来满足条件并且最长边最小
条件为牛跑来跑去后每个牛棚能容纳下
考虑二分答案,从而得到满足的边,跑一遍网络流验证解的可行性
构图:
从汇点到各个左牛棚,容量是每个牛棚原本的牛数量
拆点,从左牛棚连到右牛棚,表示可以通过去,容量是无限
从右牛棚到汇点,容量是牛棚最后的最大容纳
假如最大流=牛的数量F 表示可行
记得自己可以连自己
代码
|
|