BZOJ 1458 士兵占领

发布于 2017-05-24  155 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1458

题意:对于一个 m*n 的棋盘,放士兵,有如下限制:有 k 个格子不能放,对于每一行每一列,都有一个限制使得该行/列的士兵数大于某限制值... 士兵数量尽可能小


一眼网络流,想怎么建模,最开始想了个对于每一点建模+拆点的鬼东西... 看了题解后才明白 orz,建模还是不会呀 qwq

最大流能解决的常见模型是让答案尽可能的大,但是此题是尽可能小,其实这等价于所有能放的点都放,然后删除尽可能多的点... 于是就可以跑最大流了

我们先将能放的点都放上去,然后考虑新限制:每行/列可以最多删除多少个士兵,一行和一列都分别抽象为一个点,令 a[i] 表示 i 行最多删多少个,b[i] 表示第 j 列最多删多少个,那么建图是这样的

... 还是详见代码吧 写的还是比较清楚的

因为 N 开小了狂 TLE 不止... 说好的 RE 呢....

 


一个非常弱的准退役OIER