【文件属性】：
文件名称：《三人信523535232452345325》
文件大小：968B
文件格式：CPP
更新时间：2022-08-04 13:49:01
网络流
network-flows，网络流，传说中的省选算法
先推荐一个讲网络流思路的blog：
https://www.cnblogs.com/ZJUT-jiangnan/p/3632525.html
网络流有两种写法，dinic和sap（isap） 本人太弱了，只会dinic
目的 首先，明确网络流是干什么的
给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).
下面给出一个通俗点的解释
好比你家是汇 自来水厂是源
然后自来水厂和你家之间修了很多条水管子接在一起 水管子规格不一 有的容量大 有的容量小
然后问自来水厂开闸放水 你家收到水的最大流量是多少
如果自来水厂停水了 你家那的流量就是0 当然不是最大的流量 但是你给自来水厂交了100w美金 自来水厂拼命水管里通水 但是你家的流量也就那么多不变了 这时就达到了最大流
理解起来还好吧，也就是上文说的那样
实现 现在知道了到底要求什么了，但是怎么求？
先给个模型如下
首先来手算一下，很容易可以得