二分图 & 网络流初步
jiazhaopeng · · 个人记录
链接 ： 最小割&网络流应用
EK太低级了，不用。 那么请看：#6068. 「2017 山东一轮集训 Day4」棋盘，不用EK你试试？
dinic模板及部分变形应用见zzz大佬的博客：网络流学习笔记（反正我的码风和大佬zzz的差不多）
二分图覆盖与匹配
最小点覆盖=最大权匹配
简单（假）证明：
最小点覆盖包含的点数不可能小于最大匹配包含的边数。
尝试增广，把dfs到的点标记，那么左部未被标记的点和右部被标记的点为合法点。
求最小点覆盖的方案：详见 题解 UVA11419 【SAM I AM】
-
将用到的x和y点打上标记flag。（因为最小点覆盖的点一定连有满流的边）
-
在余量网络里dfs，将途径的点打上标记arr。
-
选择的方案(之一）为：所有打flag标记的点中：打了arr标记的x点和没打arr标记的y点（为了防记重）。
(紫圈是打了标记的点（还落掉了左上角的那个点））
2020.10.15 Update：
感觉之前写的有些问题，看不太懂了。于是向zzz问到了一种更容易理解的方法：
将二分图最小点覆盖问题看作最小割问题。割掉表示选。左右的1边和中间的
习题
-
UVA11419 SAM I AM
-
P1263 宫廷守卫
二分图最大独立集 = n（二分图总点数） - 最大匹配
证明：去掉二分图的最小点覆盖。
二分图的最小点权覆盖和最大点权独立集
不让每个点连向源汇的边容量为1，而让其为点权。跑最大流为最小点覆盖。跑最大流即为最小点权覆盖，
不愿意证明，感性理解一下吧。
习题
P3355 骑士共存问题
DAG的最小路径覆盖（=最小路径点覆盖）
例题：P2764 最小路径覆盖问题
给个DAG，要求用尽量少的路径（可以相交）（路径可以起点等于终点）覆盖所有点。
把起点集合看作左部图，终点集合看作右部图，起点向终点连边。那么 DAG总点数
简单（假）证明：
一开始不跑最大流时，相当于尚且没有选路径，“最小”路径覆盖为
较为严谨的一个证明
每条路径中点最多入一出一，如果度数还要多，就要“新建”一条路径了。
首先让路径都初始化成
每次选择一条边，就相当于将两个点的“路径”合并成为一条路径。当然，如果发现那一个点已经被合并了，那么可以跳过那个点，再从那个点的一条出边继续寻找合并的路径；或者“换掉”那一个点，即反悔操作。
找方案
模拟上面的证明。枚举左部图所有点
拓展
即便要求路径长度不可以为1，只要没有度数为0的点，那么这么求的答案仍然正确。（毕竟0路径是最差的路径，可以通过硬给它塞成一个1路径，而答案不会更劣）求方案也可以随便给0点找一条出边或入边。
但是如果要求路径不交，那可能就要拓扑DP之类的了。
习题
P2765 魔术球问题
升级版：最小可重路径点覆盖
给个DAG，要求用尽量少的路径（可以相交，且相交部分可以不止一个点）覆盖所有点。
（模仿李煜东书）如果
进一步地，我们索性全部把间接相连的点对直接连一块，那么整道题就可以像普通最小路径点覆盖那样做了。这部分可以用
似乎这种方法叫做传递闭包
Code:
//v[i][j]:邻接矩阵
for (register int i = 1; i <= n; ++i) v[i][i] = true;
for (register int k = 1; k <= n; ++k)
for (register int i = 1; i <= n; ++i)
for (register int j = 1; j <= n; ++j)
v[i][j] |= v[i][k] && v[k][j];
for (register int i = 1; i <= n; ++i) v[i][i] = false;习题
Treasure Exploration
379. 捉迷藏
最长反链与Dilworth定理
DAG 的反链指的是 DAG 上的一个点集，其中不存在点对
最长反链即为点数最多的反链。
与“最小点覆盖与最大独立集”类似，DAG的最长反链等于最小可重链覆盖。证明的话证明不可能大于最小链覆盖是显然的，证明可以达到最小链覆盖可以见下面的构造方法。
我们做完传递闭包后转为二分图，那么我们的最小链覆盖答案即为
详见r_64的题解。
经典题目：P4298 [CTSC2008]祭祀
（基本上是模板）CF590E Birthday
DAG 的不可重叠最小路径边覆盖
给一张 DAG，选择一些路径，使得这些路径能够遍历到所有边，且每条边恰好被遍历到了一次。
做法
（考虑将入边和出边拼路径）
（感觉不大对的样子）
DAG 的可重叠最小路径边覆盖
支持一种操作：选择一条路径，让其起点的 out++，终点的 in++。然后求出不可重叠最小路径边覆盖（加一串重边）
据lyd大佬的课件，“我们根据以往的经验知道，网络流寻找路径的问题，应当把每个点拆点，然后把路径拆成若干条边、以及拆点之后两个同点之间的边。” 然而我还是太年轻了，实在理解不了啊。（事实上最小路径点覆盖我都无法理解）。于是转而成为背诵内容。
• 把每个点拆成左、右两个，右点向左点连容量为+∞的边。
• 从源点S向所有in[i]>out[i]的左点连边，容量为 in[i]-out[i]。
• 从所有in[i]<out[i]的右点向汇点T连边，容量为 out[i]-in[i]。
• 对于原图中的边(u,v)，从u的左点向v的右点连容量为+∞的边。
• 求最大流，那么答案就是满流减去最大流。
• 一条边上有多少流量，就要添加多少条重边，然后dfs输出方案。注释：第四点中的“满流”指的是
事实上，可重最小路径边覆盖还有一种最小流（全称：有源汇有上下界最小流）的做法：建立一个虚拟源点
Hall定理（霍尔定理）
内容
左右部点均为
证明
显然如果二分图存在完美匹配，那么一定会符合那个性质。
如果存在那个性质，而又没有完美匹配，那么我们搞出一个最大匹配，肯定会至少有一个点不在最大匹配中。根据那个性质，这个点一定有至少一个出边集合，而出边对应的点一定是最大匹配中的点，否则存在增广路。而那个点一定会有另一个出边为匹配边，然后能再找到与匹配边相连的其它点，然后又能扩展出更多的点...最终导致矛盾。
“三分图”模型
（其实或许根本没有“三分图”这个名字）
如果我们的问题是对于一些点，其中每一个点
左边一列点
例题:P1231 教辅的组成 ；P4142 洞穴遇险 ；bzoj 1711 Dining 吃饭；P3756 [CQOI2017]老C的方块
网格图与网络流
-
见网格图要想黑白染色转二分图！这是个常见套路！（甚至例题方格图都有这个套路）有的时候不仅仅是黑白染色，还可能使黄绿蓝染色（见P3756 [CQOI2017]老C的方块）搞成三分图。
-
见网格图要想平面图对偶图，转对偶图最短路加速
-
路径或连通块想插头DP
最大流
最大流的必须边：（不确定对不对）
满流 并且 在残量网络上属于不同的SCC（强连通分量）（为了排除非必须边的可行边）。
最大流的可行边：（不确定对不对)
满流 或 在残量网络上属于不同的SCC。
例题：380. 舞动的夜晚
一条显然的性质 ： 最大流的边是具有可加性的。
如 建立
最小割
最大流等于最小割。
如何找到最小割的割边？
-
从S开始沿着残量网络BFS，把能到达的点标记上。
-
连接已标记的点和未标记的点的正向边为该网络的一个最小割集。（-by lyd大佬）
如何找最小割的必须边？
-
从S开始BFS跑残量网络。
-
从T开始反向BFS跑残量网络。
-
枚举从S指向T的满流边，这些边即为必须边
如何找某种情况的最小割的可行边？
-
满流
-
删掉后找不到u -> v的路径
于是：残余网络中tarjan跑SCC, (u, v)的u, v都在同一SCC中说明存在残量网络u -> v的路径 -by lyd大佬
习题
- P4126 [AHOI2009]最小割
网络流常用思想：点边转化思想
拆点：
把点拆成入点和出点，两点间边权为点权。或者拆成有两个特殊含义的点。
例题：
Cable TV Network
Kaka's Matrix Travels
P1251 餐巾计划问题
拆边：
对于边权比较复杂的问题（比如和第几种情况、之前选用该点次数等有关，但不管怎样都会选最小的情况作为代价），把所有情况分解成某几条边上的权值和。（类似于二进制拆分多重背包？）
如: #6068. 「2017 山东一轮集训 Day4」棋盘 ；还有P4307 [JSOI2009]球队收益 / 球队预算
一些毒瘤题
P6185 [NOI Online 提高组]序列（民间数据）
题意: 给一个长度为
数据规模：n <= 1e5。存在 t 全部为 1 和全部为 2 的数据。
根据套路想法，我们不难发现，
现在又加上
我们把隔两条边的点合并成为一个连通块，连通块内的值就可以在保证总和不变的前提下随意改变了。这种方法的实质其实是将奇环合并，将二分图的左右部图（联通的）合并成为一点。最终会剩下一些度数不超过1的点。此时模拟题意，对于一条边
比较考验代码能力，毕竟要进行那么多种合并。不过也没有那么毒。(不明白为什么考试时连60分都没拿到）
my record
注意！
- 最大独立集
= n - mxflow ， 最小点覆盖= 最大匹配= 最大流，最小路径点覆盖= n - 拆点后最大流
搞不清最好随便搞几个二分图画一画。
-
dinic的弧优化记得加，记得初始化！！别忘了s、t的初始化！！+1
-
dep/dis要初始化为0x3f，不要初始化为0！！！
-
ecnt 初始化为1，不是0！！！
-
一定要连反向边！！！！！
-
不要随便连边！！！注意边的方向！！！格外警惕
addedge(t, i, inf)这样的连边！！！ -
费用流注意一下
vis 的使用情况 -
费用流注意 SPFA 的队列要开30倍左右（大概是
<< 6；<< 5也可以，但是要是写成<< 30就不好了）
附
模板（调试用）
2021.4.18 Update:
更新了最大流板子，常数更小一些。
最大流
int que[N], front, rear;
int dep[N];
inline bool bfs() {
memset(dep, 0x3f, (n + 3) * 8);
front= rear = 0;
memcpy(hcur, head, (n + 3) * 8);
dep[s] = 0; que[++rear] = s;
while (front < rear) {
int cur = que[++front];
for (int i = head[cur]; i; i = e[i].nxt) {
int to = e[i].to; if (!e[i].val || dep[to] <= NN) continue;
dep[to] = dep[cur] + 1; que[++rear] = to;
if (to == t) return true;
}
}
return false;
}
int dfs(int cur, int limi) {
if (cur == t || !limi) return limi;
int flow = 0;
for (int &i = hcur[cur]; i; i = e[i].nxt) {
int to = e[i].to;
if (dep[to] != dep[cur] + 1) continue;
int tmp = dfs(to, min(limi, e[i].val));
if (!tmp) continue;
flow += tmp; limi -= tmp;
e[i].val -= tmp; e[i ^1].val += tmp;
if (!limi) break;
}
return flow;
}
int main() {
...
while (bfs()) {
mxflow += dfs(s, inf);
}
...
}最小费用最大流
inline bool spfa() {
memset(dis, 0x3f, sizeof(dis));
front = rear = 0;
for (register int i = 1; i <= ptot; ++i) hcur[i] = head[i];
dis[s] = 0; que[++rear] = s; vis[s] = true;
while (front < rear) {
int cur = que[++front]; vis[cur] = false;
for (register int i = head[cur]; i; i = e[i].nxt) {
int to = e[i].to;
if (dis[to] <= dis[cur] + e[i].fare || !e[i].val) continue;
dis[to] = dis[cur] + e[i].fare;
if (!vis[to]) que[++rear] = to, vis[to] = true;
}
}
return dis[t] < inf;
}
int dfs(int cur, int limi) {
if (cur == t || !limi) return limi;
vis[cur] = true;
int flow = 0, tmp, to;
for (register int i = hcur[cur]; i; i = e[i].nxt) {
to = e[i].to; hcur[cur] = i;
if (dis[to] != dis[cur] + e[i].fare || vis[to]) continue;
tmp = dfs(to, min(limi, e[i].val));
if (!tmp) continue;
flow += tmp;
limi -= tmp;
e[i].val -= tmp;
e[i ^ 1].val += tmp;
if (!limi) break;
}
vis[cur] = false;
return flow;
}
int main() {
...
int res = 0;
ll ans = 0;
while (spfa()) {
res = dfs(s, inf);
ans += dis[t] * res;
}
...
}