[BZOJ3144/Luogu3227][HNOI2013]切糕(网络流)

发布于 2018-04-06  136 次阅读


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

本文链接地址:[BZOJ3144/Luogu3227][HNOI2013]切糕(网络流)

Description

经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。

出于简便考虑,我们将切糕视作一个长 P、宽 Q、高 R 的长方体点阵。我们将位于第 z层中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z),它有一个非负的不和谐值 v(x,y,z)。一个合法的切面满足以下两个条件:

Tag

网络流

解决思路

转化为最小割,其实就是求一个权值最小的割面。
那么当没有对光滑性的限制的时候,就是求每一条竖线上的最小值,如果连成图论模型就是求每一条链上的最小割。
现在把光滑性的限制加入,即对于相邻的竖列,选择的割点的位置与当前列的差不能超过一个给定的值。
于是对于(u,v,w)的相邻的竖列,我们连边(u',v',w-k),流量为无限,这样就可以保证当我们选择了w高度时,相邻列中小于w-k的边都是不能被割掉的;两边一起限制,就可以使得题目的要求得以实现。

代码

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

本文链接地址:[BZOJ3144/Luogu3227][HNOI2013]切糕(网络流)


HNCJ OIer