POJ 3084 最小割

题意:

有n个房间,要确保一个特定房间不能进坏人(初始有若干房间有坏人)。相邻的房间可能会有门,但是门上的锁是单向的(只能从一个房间打开进入另一个房间,

a b ,只能从a进入b  不能从b 进入a),初始所有的锁都是开着的,问至少关上几个锁,才能不让坏人进入那个房间。

题解:
人不就相当于流么?!最小割~

不想说建图了,唯一要注意的就是锁是单向的。

对于a和b之间的门,若a有锁,b没有锁,那么连接a-->b容量INF(这个门锁了白锁,坏人自己能打开),b-->a容量1

困了,今天不想写题了。。就只想了想怎么建图。。

代码参考:http://blog.sina.com.cn/s/blog_6af663940100m23o.html

没有人能阻止我前进的步伐,除了我自己!
原文地址:https://www.cnblogs.com/proverbs/p/2850396.html