最大流
常用的算法： Edmond-Karps 和 Dinic
无源汇有上下界可行流
首先明确问题：现在这个问题叫做 “可行流” 而不是 “最大流”，是因为现在有了额外的每条边流量上下界的要求，所以未必存在一个流满足所有这些条件。
假设一条边的流量下界是 、上界是 ，则基本的想法是先固定让这条边流过 ，然后剩下的 放在算法里跑。但是如果直接把这个边的流量预先设为 ，建好的图不一定满足对于每个点都有流出等于流入。
解决方法是建立一个超级源点 和一个超级汇点 ，在跑算法之前先看一下每个点是否有不平衡的情况，如果有净流入 ，则让 与当前点连接一条容量为 的边；如果有净流出，则让当前点与 连接一条容量为 的边，这样算上 和 之后整体还是平衡的。
然后从 到 跑一遍最大流，此时的 “最大” 是没有意义的，只是借助这个算法找到一组可行解。判断是否可行的条件是刚才连的 的那些出边、以及 的那些入边是否流满。
有源汇有上下界可行流
这个问题在上一个的基础上加入了指定的源点 和汇点 。考虑多出来的这个要求，实际上只需要满足源点的流出量恰好等于汇点的流入量即可，因为这两个点不满足流量平衡。所以只需要额外加入一条从 到 的、容量无穷大的边，然后再按照刚才的方法跑一遍最大流就行了。
有源汇有上下界最大流
先跑一遍可行流来把超级源汇的边流满，然后再跑一遍从 到 的最大流即可。这不会影响超级源汇的流值。
有源汇有上下界最小流
先跑一遍可行流来把超级源汇的边流满，然后再跑一遍从 到 的最大流。注意，此时从 到 的那个多余边容量是无穷大，所以最大流算法总是会优先在这条边上增广。所以必须先删掉这条边才行。
费用流
最小费用最大流
最经典的是最小费用最大流，这个问题是在保证流值最大的情况下，求总费用最小的方案。只需把 Dinic 算法中 BFS 分层的过程改成根据费用跑最短路即可。同时，建反向边时需要保证费用也取相反数。
最小费用（有上下界可行）流
这个问题不等于最小费用最大流，因为总费用最小并不代表着流量最大。实际上，这类费用流的问题大致可以分解成最短路 + 最大流相关问题。比如，最小费用可行流就是在有源汇可行流的基础上，把 BFS 改成最短路。
但是在有负费用的情况下，只能用 Bellman-Ford 这类算法求最短路，它们无法解决图中存在负费用环的情况。这种情况下可以用两条边来等效出一条负费用边。
- 一条边是原本的边，但是强制它跑满流量。强制的方法就是用有上下界可行流的方法，与超级源汇进行相应的连边。
- 另一条边是反向边，流量没有额外的限制，但费用变成正的。实际上在正常的建边过程中反向边的费用就应该是相反数，我们只是模拟了这个过程。
Dinic 时间复杂度
- 一般网络：，单轮增广复杂度
- 各边容量为 的网络：，单轮增广
- 单位网络（各边容量为 并且除了源汇之外各点入度或出度不超过 ）：，单轮增广
常用转化
最小割
选择一个子图，使得它到其他点的出边的总容量最小。
答案为 最大流。
最大权闭合子图
每个点有点权 ，需要找到一个子图使得：
- 对于每个边 ，如果 在子图中，则 也在子图中；
- 子图的点权和最大。
进行如下建图：
- 源点向正点权的点连接容量为点权的边；
- 负点权的点向汇点连接容量为点权绝对值的边；
- 原图中的边保持不变，容量为 。
答案为 正点权之和减去最小割。
最小路径覆盖
在有向无环图中，找到最少的不相交路径个数，使得这些路径经过了所有的点。 将每个点 拆成 和 两个点，对于每条边 ，在新图上连边 ，这样得到一个二分图。
答案为 原图的节点数减去新图的最大匹配数。
如果路径可相交，则先求出原图的传递闭包，如果 到 有路径，则连边 。然后在闭包上跑最小路径覆盖。
二分图最小点覆盖
选最少的点，满足每条边至少有一个顶点被选择。
答案为 最大匹配。
二分图最大独立集
选最多的点，满足两两之间没有边相连。
答案为 总点数减去最小点覆盖。