网络流技巧

模拟费用流

费用流模型是一类非常优秀的模型，但是用于解决费用流问题的常规算法大都比较鸡肋，因此在一些特殊的网络上可以使用模拟费用流的思想来解决此类问题。模拟费用流没有固定的模板，只能算一种思想，在这里只能是大致分类一下。

wqs 二分

反悔贪心

模拟费用流

直接模拟增广的过程，即模拟 寻找增广路->累计答案->推流 这一过程。

【某模拟赛题】 给定平面上 \(n\) 个黑点和 \(n\) 个白点，你需要将其两两匹配，使得曼哈顿距离和最大。

暴力的建图费用流是平凡的，可以坐标相同的点压缩。

考虑把曼哈顿距离转化成切比雪夫距离（\((x,y)\to(x+y,x-y)\)），在新的坐标系下两点距离变成了 \(\max(|x_i-x_j|,|y_i-y_j|)\) 容易发现只有四种取值，于是有一种不那么暴力的做法，对四种取值建四个点后跑费用流，建图如下：

图中容量全为 \(1\)。为了方便，称 S,T,中转点为关键点，定义 \(val_{p,v}\) 为某个非关键点 \(p\) 到关键点 \(v\) 的边权。

模拟费用流，考虑到一条增广路一定形如 S->黑点->中转点->黑点->中转点……->白点->T，并且容量全为 \(1\)，而关键点之间在增广之前的最长路是确定的。这启发我们可以舍弃大量的黑点白点，只维护关键点之间的最长路，大致的算法分为两步：

1. 求一条最长路
2. 对最长路进行增广

具体实现上，我们用 \(6\times6\) 个带删堆维护关键点之间的最长路，初始时中转点之间都是不连通的，所以只初始化到 S、T 的最长路即可。

第一步可以暴力建出一个 \(6\times6\) 的完全图，每条边的权值都是两点间的最长路，在这张图上跑出一条从 S 到 T 的最长路即我们要求的增广路。

第二步可以对每一条增广路上的边分情况讨论（因为总长不超过 5）。注意这里的一条“边”实际上相当于原图上两条边（关键点->非关键点->关键点），要维护的东西就是删掉当前的边并加上反向边。

只讨论一半的情况，另一半同理。

• \(S\to P\to X\)：对于所有 \(V\) 删除一条边权为 \(val_{P,V}\) 的边，对于所有 \(V\not=X\)，加入一条边权为 \(-val_{P,X}+val_{P,V}\) 的边。
• \(X\to P \to Y\)：对于所有 \(V\not= X\)，删掉一条边权为 \(-val_{P,V}+val_{P,X}\) 的边，对于所有 \(V\not= Y\) 加入一条边权为 \(-val_{P,Y}+val_{P,V}\) 的边。

重复这个过程 \(n\) 遍（因为最大流为 \(n\)，要找到 \(n\) 组匹配）就能得到答案。