BZOJ 1412 [ZJOI2009] 狼和羊的故事

发布于 2017-05-09  136 次阅读


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

题意:一个 n*m 的网格图,边框均为篱笆,有一些点是狼,一些点是羊,在边上建篱笆,使得狼吃不到羊,一单位长度的篱笆费用为 1.


初学网络流... 结果找不到裸题,这个算是比较好建模的了。

对于每一只狼,和源点建一条边权为 inf 的边,对于每一只羊,和汇点建一条边权为 inf 的边.

对于每一个格子,与它的四周连边权为 1 的边,这样建图后只要汇点有流到就说明狼吃到了羊,于是求最小割即可,即最大流

代码如下:

 


一个非常弱的准退役OIER