网络最大流（dinic）

模型

在一张图中,给定一个源点s,给定汇点t,点之间有一些水管，每条水管有一个容量，经过此水管的水流最大不超过容量，问最大能有多少水从s流到t（s有无限多的水）。

解法

dinic算法通过不断寻找增广路的方法得到最大流。

增广路：从源点开始通过一些边到达汇点的边集称为一条增广路。

显然，通过一条增广路的水流是有最小限制的，其就等于增广路上水管最小的通过量。

通过寻找一条条增广路，每次找到后经过的边权都减去最大流量，并将答案加上最大流量，就得到了部分解。

但是部分解不一定是最优的，因为程序不存在反悔机会。比如

对于此图来说如果先找到的增广路是1->2->4->6,在下一次寻找中,1->3->4然后就会发现无路可走了，得出的答案就是1，实际上如果走1->2->5->6和1->3->4->6答案为2，显然更优。

所以，我们在找到一条增广路后需要将经过的路径反向建边构*悔的路径如图

这是第一次增广选择1->2->4->6之后，对于经过的边反向建立反悔边，如果此时继续寻找增广路，就会选择1->3->4->2->5->6。这两条路径相结合，实际上就是走了1->2->5->6和1->3->4->6这两段。所以在寻找完增广路后反向建边，可以使答案不出问题。

但是这样的做法其实是EK算法，它会被某些特殊数据卡住。如图