upd: (2021.7.28 时隔一个月再来，感觉我已经忘完了，但还是 push 这篇吧)

前言

最近想重新学一些算法，比如网络流来了。

最大权闭合子图

最大权傻逼子图。

解决这样一类问题：每个对象对于全局有他的价值，而对象之间又有依赖的问题，就是说选了某个对象必须要选个对象，使得全局总收益价值最大。

建图：

• 对于正权的，源点 $s$ 连向它，边权为正权。

• 对于负权的，连向汇点 $t$，边权为负权的绝对值。

• 对于依赖关系，假设 $a$ 依赖 $b$，就是 $a$ 需要 $b$，那么 $s$ 向 $t$ 建一条为 $inf$ 的边。

• 这样建图跑最大流，正权和-最大流就是答案。

  为什么对呢？

• 最大流的值等于最小割的值，割是去掉这些边后使得从 $s$ 到 $t$ 不存在路径的边集。

• 考虑这张图的最小割，由于依赖关系容量是 $inf$，不可能成为最小割的边集，只会割 $s$ 到正权点，或者负权点到 $t$。对于正权，保留的是决定要的，割掉是不要的，对于负权，割掉的是决定要的，保留的是不要的。

• 割就是使得从 $s$ 到 $t$ 不存在路径的边集嘛，正权和是所有可以获得，最小割是最小的去掉的东西。

• 对于一组左边一个点到右边一堆点的依赖关系，你要么割左边的，直接不要它。假如你不割左边，那么你必须割掉它右部所有依赖的点，才能使得从这个点到 $t$ 没有路径，于是就相当你决定要这些负权点(最小割减去)，割部分右边依赖的点，无法使得割的概念成立。

• 理解差不多就这么些，确实挺傻逼的。

• 输出方案的话，根据是否被割，那割边怎么找？最后一次失败分层, 无法到达汇点，路径上经过的可达都是要的，正权，无法到，因为边被割了，符合不要，负权，可以到了这个点，后继边满流被割了，符合要。

• 所以只需要 $d$ 数组非零即可。

• 最大权傻逼子图。

最小路径覆盖

处理一类最小路径覆盖问题(…

比如有向图用最少的路径覆盖他们，每条边只能用一次，可以用网络流的模型来限制。

• 建图：
• 每个点拆成两个点，代表入点和出点，如有一条边 $u->v$，则建边 $u -> v+n$
• 这样跑 n-最大匹配数 就是答案.
• 为什么对呢，假设啥边没有，肯定是 n 条路径吧，每个路径都是自己点。
• 每多一条匹配边，那么意味着可以合并两条路径，就是说头和尾相接起来，会使得答案 $-1$，就得到了匹配数加一，路径数减一的结论。
• 也非常简单。
• 输出方案只需要知道，每个左部点他的匹配对象是啥，然后你只需要找一个右部不被入的点开始往下走就好了。
• 网络流 24 题里还有一个，就是说，给定 $n <= 55$ 个柱子，叫你顺次放 $1，2，3…$，每次只能放在柱子顶部，要求相邻两个数字必须和是平方数，求最多能放多少个数字，输出方案。
• 稍微变了变，就是给定路径数，不难想到二分一下答案，给定数，需要最少多少路径，就做完了。

分层图

给正整数序列，$x_1…x_n$，求最长不下降子序列长度 $s$。$(n<=500)$

每个元素只允许用一次，求最多可取多少个长度为 $s$ 的不下降序列。

如果允许多次用 $x_1$ 和 $x_n$，序列里最多可取多少个不同的长度为 $s$ 的不下降序列。

• 第一题，显然 $LIS$ 就可以解决。
• 第二题，注意到每个元素只允许用一次，不难想到拆点，中间建立一条边，容量为 1 限制用一次，那源点连啥，汇点连啥呢？
• 考虑 $dp$ 值，$dp_i$ 代表以 $i$ 结尾的 $LIS$ 长度，那么源自然连向 $dp_i$ 为 1 的点，$dp_i$ 为 s 的点连向汇，而中间的联系，就是 $dp_i+1=dp_j \and x_i<=x_j$，其实挺自然的。
• 这样跑最大流就能满足第二题的要求，所有可能的联系都建立了起来，且限制只使用一次，思想大概是根据 $dp_i$ 来分层。
• 第三题，只需要将 $x_1$ 和 $x_n$ 本身和源汇之间容量特殊化为 $inf$ 即可，需要注意 $ n ==1$ 的时候，不要源汇都连 $inf$。

二分图最大点权独立集

方格取数问题，给方格，每个点有点权，不能同时取相邻的数，求最大和。

发现限制是相邻，网格图肯定是二分图，可以被剖成两个集合，格点之间存在互斥关系，取了一个不能取另一个。

把求最大取得和，转化为去掉最小的数，使得所取数不存在互斥关系。

• 这样的模型，转化为最小割。
• 我们可以把每个点的点权转化为最小割的一条割边，割掉代表要去掉，而互斥关系 从左部向右部建立一条 $inf$ 的边，不可能被割。
• 那么最小割后的图，就能使得不存在增广路，那么剩下的点之间就不存在互斥关系，否则还能通过互斥关系增广矛盾。

然后就 $sum-maxflow$ 就做完了。

最小割

经典问题模型

有 $n$ 个物品和两个集合 $A,B$，如果将一个物品放入 $A$ 集合会花费 $a_i$，放入 $B$ 集合会花费 $b_i$；还有若干个形如 $u_i$, $v_i$, $w_i$ 限制条件，表示如果 $u_i$ 和 $v_i$ 同时不在一个集合会花费 $w_i$。每个物品必须且只能属于一个集合，求最小的代价。

这是一个经典的 二者选其一 的最小割题目。最小割是个很好的工具，就可以将点集划分成两半，一些属于源点，一些属于汇点。割边可以看成去掉的，就是你的代价。

最小割就是最小花费。

无源汇上下界可行流

对于一个有向图，每条边有一个流量下界和流量上界，你要给出一个可行流使得每条边的流量满足上下界，且满足整个网络的流量守恒。也称 循环流。

• 怎么做呢，不妨假设每条边都先取到了下界，那么新边的容量就是 $R-L$，就以这样的流量网络作为初始流，但光初始流存在问题，肯定不一定满足流量守恒。

流量守恒就是每个点的总流入流量等于总流出流量。

• 现在需要加入新的流量，称作附加流，来使得每个点的流量平衡，怎么加呢？
• 对于初始流 $流入>流出$ 的点，那么对于附加流，我们需要 $流入<流出$，流出更多，因此需要新源点 $S$ 来提供流量。
• 对于初始流 $流入<流出$ 的点，那么对于附加流，我们需要 $流入>流出$，流入更多，因此需要新汇点 $T$ 来接收流量。

然后用 $dinic$ 来求解流量守恒的有源汇 $S->T$ 最大流即可。

每条边的答案就是，下界加上 $dinic$ 里的 $R-L$ 边中的附加流流量。

有源汇上下界可行流

对于一个有向图，有源点和汇点，每条边有流量上界和下界，你要给出一个可行流，使得所有边流量满足上下界，且所有点流量守恒，当然源点流出流量等于汇点流入流量。

• 考虑将源点和汇点转化为一般点，就可以套用无源汇上下界可行流的模型。

为了做到这一点，注意到 $源点s$ 的流出量等于 $汇点t$ 的流入量，我们可以从汇点 t 向 $源点s$ 连一条下界为 $0$，上界为 $inf$ 的边，相当于把 $源点s$ 流出的流量在从 $t$ 流回来。

这样就转化为上面的题，可以新增超级源汇点 $ss$，$tt$，求一个可行流即可。

最后得到的可行的有源汇流的流量，就是新增的 $t->s$ 边中的流量。

有源汇上下界最大流

题面还是一样，但是此处流量需要尽可能大，即在可行流基础上总流量尽可能大，给出一个最大流。

继续套用模型，先求一个有源汇上下界的可行流，但这样的流不一定最大。

需要在残量网络上继续跑 $s->t$ 最大流，把 新的增广的出流量 + 之前求出的可行流 即可。

注意要在残量网络上跑，只需把 $ss$ 和 $tt$ 相关的边，和 $t->s$ 的边 $cap$ 禁一下即可。

有源汇上下界最小流

题面一样，流量需要尽可能小，即在可行流基础上总流量尽可能小。

套用模型，残量网络上 $t->s$ 最大流，之前求出的可行流 - 新的增广的出流量。

带下界的费用流？

根据有无源汇，上下界，可行流与上面一样，使得所有点源汇平衡。