网络流杂记

Dinic算法理解

• 第一次dfs找到有可能还有流量的边并且分层
• 每一次dfs到\(t\)代表的是一条增广路被找到。
• 回溯途中所有的点以及反向流量都得到改变，对于每一条增广路来说都减去一个固定的值。
• 从汇点到源点的按照dfs回溯过程依次将贡献合并，每个边在对应得dfs回溯过程中减去相应的值，而减去总值在回溯过程中又可以不断累加，直到回到源点，每个dfs返回的是这个点累加的总流量。
• 当前弧优化：当我们从一个边走出后这个边后面的资源已经耗尽了很多了，不如这次就不走这个边了，也就是说在一个dfs中每个边只经历一次，可以使用一个now数组代表当前到哪个边了。
• 反向边如果是顺序存储的，可以用奇偶探边法

杂记：二分图的小性质

必须边：不属强连通分量，已经属于匹配

可行边：属于强连通分量，不属于匹配

对于非完备匹配只能用最大流剩余流量1流的方向建图即可。

最大流最小割定理

\(s\)和\(t\)的最小割等于\(s\)和\(t\)的最大流

费用流

适用EK，刚开始SPFA找到残留网络上一条\(s->t\)的最短路(记录路径)，后在这条记录路径上处理就好。

反边本质

反悔，但这个反悔很妙，让我自己发明是发明不出来的。

具体来说

美妙字体（）