[BZOJ2132/Luogu1935]圈地计划(网络流)

发布于 2018-02-03  4 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2132/Luogu1935]圈地计划(网络流)

Description

最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解,这块土地是一块矩形的区域,可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境,每块小区域建造商业区和工业区能取得不同的经济价值。更具体点,对于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益,即如果区域(I,j)相邻(相邻是指两个格子有公共边)有K块(显然K不超过4)类型不同于(I,j)的区域,则这块区域能增加k×Cij收益。经过Tiger.S教授的勘察,收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么?

Http

BZOJ
Luogu

Tag

网络流

解决思路

最小割模型。
转化为把所有收益求和后算出最少损失,变成最小割模型。
一个格子建工业区还是商业区这个比较好处理,但若不同类型的格子相邻产生收益这不好处理。
一个格子与其相邻四个格子产生可能的收益,我们发现这个分类与黑白染色很像。
所以我们把格子黑白染色,假设白格子先选工业区,黑格子选商业区,那么相当于一开始所有的相邻不相同的收益都是可以得到的,然后再建图跑最大流。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2132/Luogu1935]圈地计划(网络流)


HNCJ OIer 一枚