[BZOJ2007/Luogu2046][Noi2010]海拔(网络流,平面图对偶图,最短路)

发布于 2018-02-25  136 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2007/Luogu2046][Noi2010]海拔(网络流,平面图对偶图,最短路)

Description

YT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×n个区域。简单起见,可以将YT市看作一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路(简称道路),每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2),城市被划分为2×2个区域,包括3×3个交叉路口和12条双向道路。 小Z作为该市的市长,他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量,即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值,YT市市民认为爬坡是一件非常累的事情,每向上爬h的高度,就需要消耗h的体力。如果是下坡的话,则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数),那么一个人经过这段路所消耗的体力是max{0, h}(这里max{a, b}表示取a, b两个值中的较大值)。 小Z还测量得到这个城市西北角的交叉路口海拔为0,东南角的交叉路口海拔为1(如上图所示),但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下(即你可以任意假设其他路口的海拔高度),每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。

Http

BZOJ
Luogu

Tag

网络流,平面图对偶图,最短路

解决思路

不要被题目输出要求什么四舍五入吓到了,看到左上角海拔为\(0\),右下角海拔为\(1\),那么可以贪心地猜想,图中每一个点的海拔分别是\(0\)或者是\(1\),并且\(0\)和\(1\)一定是连成一块的。那么也就是说,贡献答案的部分就是\(0\)和\(1\)交界的地方。问题转化为最小割问题。
由于数据范围较大,不能直接用网络流解决,那么考虑到这个图是平面图,所以可以转成对偶图来求最短路。
转成最短路需要注意的是,由于原平面图中正反两个方向的边的容量是不一样的,所以在对偶图中正反边的权值也是不一样的。那么为了保证顺序不变,这里选择的建图方向是,原来西到东和北到南的边在对偶图中从源点方向指向汇点方向,而原来东到西和南到北的边则在对偶图中由汇点方向指向源点方向。这样求最短路即为原图的最小割。
这里用\(Dijkstra\)实现最短路。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2007/Luogu2046][Noi2010]海拔(网络流,平面图对偶图,最短路)


HNCJ OIer