时间戳

首页 > 技术文章 > 二分图&网络流初步

二分图&网络流初步

JiaZP 2020-07-21 08:13 原文

链接 ： 最小割&网络流应用

EK太低级了，不用。 那么请看：#6068. 「2017 山东一轮集训 Day4」棋盘，不用EK你试试？

dinic模板及部分变形应用见zzz大佬的博客：网络流学习笔记（反正我的码风和大佬zzz的差不多）

二分图覆盖与匹配

最小点覆盖=最大权匹配

简单（假）证明：

最小点覆盖包含的点数不可能小于最大匹配包含的边数。

尝试增广，把dfs到的点标记，那么左部未被标记的点和右部被标记的点为合法点。

求最小点覆盖的方案：详见 题解 UVA11419 【SAM I AM】

  1. 将用到的x和y点打上标记flag。（因为最小点覆盖的点一定连有满流的边）

  2. 在余量网络里dfs，将途径的点打上标记arr。

  3. 选择的方案(之一）为：所有打flag标记的点中：打了arr标记的x点和没打arr标记的y点（为了防记重）。

最小点覆盖

(紫圈是打了标记的点（还落掉了左上角的那个点））

2020.10.15 Update：

感觉之前写的有些问题，看不太懂了。于是向zzz问到了一种更容易理解的方法：

将二分图最小点覆盖问题看作最小割问题。割掉表示选。左右的1边和中间的 \(\infty\) 边表示左右1边中至少要割掉一个，代表左右点至少要选一个。这样，最小割完以后再找个最小割集即可。如何找？从S开始遍历，遍历到的满流的正向边。

习题

二分图最大独立集 = n（二分图总点数） - 最大匹配

证明：去掉二分图的最小点覆盖。

二分图的最小点权覆盖和最大点权独立集

不让每个点连向源汇的边容量为1，而让其为点权。跑最大流为最小点覆盖。跑最大流即为最小点权覆盖， \(n - maxflow\) 即为最大点权独立集。

不愿意证明，感性理解一下吧。

习题

P3355 骑士共存问题

DAG的最小路径覆盖（=最小路径点覆盖）

例题：P2764 最小路径覆盖问题

给个DAG，要求用尽量少的路径（可以相交）（路径可以起点等于终点）覆盖所有点。

把起点集合看作左部图，终点集合看作右部图，起点向终点连边。那么 DAG总点数 \(n\) - 在二分图上跑出来的最大流 \(flow\) = 最小路径覆盖。

简单（假）证明：

一开始不跑最大流时，相当于尚且没有选路径，“最小”路径覆盖为 \(n\)。跑最大流，每找到一条增广路，就相当于找到一条边，连接了两个点，“最小”路径覆盖减去1.所以最终 \(n\) - \(flow\) 即为最小路径覆盖。

较为严谨的一个证明

每条路径中点最多入一出一，如果度数还要多，就要“新建”一条路径了。

首先让路径都初始化成 \(n\) 条长度为0的路径。然后要求尽可能多得合并路径。

每次选择一条边，就相当于将两个点的“路径”合并成为一条路径。当然，如果发现那一个点已经被合并了，那么可以跳过那个点，再从那个点的一条出边继续寻找合并的路径；或者“换掉”那一个点，即反悔操作。

找方案

模拟上面的证明。枚举左部图所有点 \(u\)，如果他的一条正向出边 \((u~ -> v)\) 满流，说明选择了这条边，这条边在最小路径覆盖的边集中。

拓展

即便要求路径长度不可以为1，只要没有度数为0的点，那么这么求的答案仍然正确。（毕竟0路径是最差的路径，可以通过硬给它塞成一个1路径，而答案不会更劣）求方案也可以随便给0点找一条出边或入边。

但是如果要求路径不交，那可能就要拓扑DP之类的了。

习题

P2765 魔术球问题

升级版：最小可重路径点覆盖

给个DAG，要求用尽量少的路径（可以相交，且相交部分可以不止一个点）覆盖所有点。

（模仿李煜东书）如果 \(u~->~p~->~v\) 且 \(x~->p~->y\)，那么我们把 \(x\) 和 \(y\) 直接连一块，再按照普通的最小路径点覆盖做即可。

进一步地，我们索性全部把间接相连的点对直接连一块，那么整道题就可以像普通最小路径点覆盖那样做了。这部分可以用 \(Floyd\) 思想实现

似乎这种方法叫做传递闭包

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 上的一个点集，其中不存在点对 \(u,v\)，使得 \(u\) 能到达 \(v\)。

最长反链即为点数最多的反链。

与“最小点覆盖与最大独立集”类似，DAG的最长反链等于最小可重链覆盖。证明的话证明不可能大于最小链覆盖是显然的，证明可以达到最小链覆盖可以见下面的构造方法。

我们做完传递闭包后转为二分图，那么我们的最小链覆盖答案即为 \(n - mxflow\)。求一个最大独立集，大小为 \(2n-mxflow\)。我们将左右两部的对应点都在最大独立集的点加入到最长反链中。显然这是反链，并且大小至少是 \(n - mxflow\)。

详见r_64的题解。

经典题目：P4298 [CTSC2008]祭祀

（基本上是模板）CF590E Birthday

DAG 的不可重叠最小路径边覆盖

给一张 DAG，选择一些路径，使得这些路径能够遍历到所有边，且每条边恰好被遍历到了一次。

做法

（考虑将入边和出边拼路径）

\[ans = \sum in[x]-out[x] \]

（感觉不大对的样子）

\[ans = m - \sum \max(in[x] - out[x]) \]

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输出方案。

注释：第四点中的“满流”指的是 \(S\) 点连向的容量之和。

事实上，可重最小路径边覆盖还有一种最小流（全称：有源汇有上下界最小流）的做法：建立一个虚拟源点 \(S\) 向所有点连 \([0,\infty)\) 的边，表示可以从任意点开始；所有点向一个虚拟汇点连 \([0,\infty)\) 的边，表示可以从任意点结束；原图中的边的上下界为 \([1,\infty)\)，表示至少经过一次。然后跑有源汇有上下界最小流，最小流即为答案。

Hall定理（霍尔定理）

内容

左右部点均为 \(n\) 的二分图中，如果在左部点中任选一个点集，其邻居集合大小不小于该集合的大小，那么该二分图一定存在完美匹配。反之亦然。

证明

显然如果二分图存在完美匹配，那么一定会符合那个性质。

如果存在那个性质，而又没有完美匹配，那么我们搞出一个最大匹配，肯定会至少有一个点不在最大匹配中。根据那个性质，这个点一定有至少一个出边集合，而出边对应的点一定是最大匹配中的点，否则存在增广路。而那个点一定会有另一个出边为匹配边，然后能再找到与匹配边相连的其它点，然后又能扩展出更多的点...最终导致矛盾。

“三分图”模型

（其实或许根本没有“三分图”这个名字）

如果我们的问题是对于一些点，其中每一个点 \(i\) 必须和集合 \(S_i\) 中的一个点匹配，同时必须和集合 \(T_i\) 中的一些点匹配，并且这些点的 \(S\) 和 \(T\) 集合互不交叉，且这些点不属于 \(S,T\) 中的任何一个集合，那么我们可以用“三分图”模型来解决。

左边一列点 \(S\)，右边一列点 \(T\)，中间一列点 \(i\)，中间向两边匹配跑（最小费用）最大流即可。

例题:P1231 教辅的组成 ；P4142 洞穴遇险
 ；bzoj 1711 Dining 吃饭；P3756 [CQOI2017]老C的方块

网格图与网络流

  1. 见网格图要想黑白染色转二分图！这是个常见套路！（甚至例题方格图都有这个套路）有的时候不仅仅是黑白染色，还可能使黄绿蓝染色（见P3756 [CQOI2017]老C的方块）搞成三分图。

  2. 见网格图要想平面图对偶图，转对偶图最短路加速

  3. 路径或连通块想插头DP

最大流

最大流的必须边：（不确定对不对）

满流 并且 在残量网络上属于不同的SCC（强连通分量）（为了排除非必须边的可行边）。

最大流的可行边：（不确定对不对)

满流 或 在残量网络上属于不同的SCC。

例题：380. 舞动的夜晚

一条显然的性质 ： 最大流的边是具有可加性的。

如 建立 \((u, v, val1)\) 和 \((u, v, val2)\) 就相当于建立 \((u, v, val1 + val2)\)

最小割

最大流等于最小割。

如何找到最小割的割边？

  1. 从S开始沿着残量网络BFS，把能到达的点标记上。

  2. 连接已标记的点和未标记的点的正向边为该网络的一个最小割集。（-by lyd大佬）

如何找最小割的必须边？

  1. 从S开始BFS跑残量网络。

  2. 从T开始反向BFS跑残量网络。

  3. 枚举从S指向T的满流边，这些边即为必须边

如何找某种情况的最小割的可行边？

  1. 满流

  2. 删掉后找不到u -> v的路径

于是：残余网络中tarjan跑SCC, (u, v)的u, v都在同一SCC中说明存在残量网络u -> v的路径 -by lyd大佬

习题

网络流常用思想：点边转化思想

拆点：

把点拆成入点和出点，两点间边权为点权。或者拆成有两个特殊含义的点。

例题：

Cable TV Network

Kaka's Matrix Travels

P1251 餐巾计划问题

拆边：

对于边权比较复杂的问题（比如和第几种情况、之前选用该点次数等有关，但不管怎样都会选最小的情况作为代价），把所有情况分解成某几条边上的权值和。（类似于二进制拆分多重背包？）

如: #6068. 「2017 山东一轮集训 Day4」棋盘 ；还有P4307 [JSOI2009]球队收益 / 球队预算

一些毒瘤题

P6185 [NOI Online 提高组]序列（民间数据）

题意: 给一个长度为 \(n\) 的序列 \(a\)。并且给 \(m\) 种操作：\(t, u, v\)，\(t=1\)表示 \(u, v\) 可以同时加或减一个数； \(t = 2\) 表示 \(u, v\) 可以一个加上个数，另一个减去相同的数。询问能否将 \(a\) 全部变成0.

数据规模：n <= 1e5。存在 t 全部为 1 和全部为 2 的数据。

根据套路想法，我们不难发现， \(t = 2\) 时不改变两数之和， \(t = 2\) 时不改变两数之差。如果 \(t_i = 2(1 <= i <= m)\)，那么我们将 \(u_i, v_i\) 连边，如果所有连通块的权值都为0，那么有解，否则无解。

现在又加上 \(t = 1\)，发现 \(u, v\) 之差是不改变的，但是这并不好办（毕竟不是相邻的差）。但是，如果学过“混合图欧拉回路”的网络流解法，我们应该能发现这种操作也是具有一定的传递性的，并且是隔项传递的。这有点像二分图，因此二分图解法是本题的解法之一。一种简便的方法:

我们把隔两条边的点合并成为一个连通块，连通块内的值就可以在保证总和不变的前提下随意改变了。这种方法的实质其实是将奇环合并，将二分图的左右部图（联通的）合并成为一点。最终会剩下一些度数不超过1的点。此时模拟题意，对于一条边\((u, v)\)，要求 \(val[u] = val[v]\)；对于边 \((u, u)\)，要求 \(u\) 的值为偶数。对于度数为 0 的点，要求其值为0.

比较考验代码能力，毕竟要进行那么多种合并。不过也没有那么毒。(不明白为什么考试时连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;
	}
	...
}

推荐阅读