Day4 网络流与二分图-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day4 网络流与二分图。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

之前那篇博客是在入门网络流时写的，现在对网络流重新有了一定的理解。

学习笔记

1. 最大流

【模板】最大流

FF 增广思想

Ford–Fulkerson 增广，核心即不断找增广路并增广。

dfs 实现

// dfs : 流入 u 的流量为 sum, 求流出的最大流
int dfs(int u, int sum) 
{
	if(sum == 0 or u == t) return sum;
	
	vis[u] = true;
	
	int flow = 0;
	for(int v = 1; v <= n; v++)
	{
		if(!vis[v] and r[u][v] > 0)
		{
			//找 u 到 t 路上的最小限制并增广
			int delta = dfs(v, min(sum, r[u][v]));
			r[u][v] -= d, r[v][u] += d;
			flow += delta, sum -= delta;
		}
	}
	return flow;
}

FF brute code

这种方法的复杂度与最大流 $f$ 有关，至多执行 $f$ 轮 dfs，时间复杂度 $O (n f)$ 。

bfs 实现 / EK

FF 增广的 bfs 实现也称 EK 算法。

// bfs 寻找增广路
bool bfs()
{
	memset(d, 0, sizeof(d)); memset(pre, 0, sizeof(pre));
	
	d[s] = 1, q.push(s); 
	
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int v = 1; v <= n; v ++)
			if(d[v] == 0 and r[u][v] > 0)
				pre[v] = u, d[v] = d[u] + 1, q.push(v);
	}
	
	return d[t];
}

// 找到增广路后增广
int augment()
{
	int flow = 1e9;
	for(int a=t; a!=s; a=pre[a]) flow = min(flow, r[pre[a]][a]);
	for(int a=t; a!=s; a=pre[a]) r[pre[a]][a] -= flow, r[a][pre[a]] += flow;
	return flow;
}

FF EK code

EK 算法的时间复杂度是 $O(nm^2)$ 。

证明：每条边至多做 $\dfrac n 2$ 次增广路上的关键边。
OI-wiki

Dinic

通过 bfs 找增广路并对图分层标记，每次 dfs 只访问下一层的结点。

同时加上当前弧优化，即不重复访问增广到极限的边，维护第一条有必要尝试的边。
有必要这样做的原因是如果一个节点有大量出边与入边，挨个遍历可能会 $O(|E|^2)$ 。
可以这样做的原因是因为每一遍增广过程中，遍历出边的顺序都是一样的。

注意在流入 $u$ 的流量为 $0$ 时要退出，否则会导致当前弧优化的出错。

时间复杂度 $O(n^2m)$ 。

bool bfs()
{
	memset(d, 0, sizeof(d)); 
	d[s] = 1, q.push(s); 
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i=head[u]; i; i=e[i].nxt)
		{
			int v = e[i].to;
			if(d[v] == 0 and e[i].r > 0)
				d[v] = d[u] + 1, q.push(v);
		}
	}
	return d[t];
}

int dfs(int u, int sum) // dfs 流入 u 的流量为 sum
{
	if(sum == 0 or u == t) return sum;
	
	int flow = 0;
	
	for(int i=cur[u]; i; i=e[i].nxt) 
	{
		cur[u] = i; // 当前弧优化
		int v = e[i].to;
		if(d[v] == d[u] + 1 and e[i].r > 0)
		{
			int d = dfs(v, min(sum, e[i].r));
			e[i].r -= d, e[i ^ 1].r += d;
			flow += d, sum -= d;
		}
	}
	
	return flow;
}

Dinic code

2. 二分图最大匹配

飞行员配对方案问题

二分图：对于 $G (V, E)$ ，分成两个点集 $V 1, V 2$ ，对于所有的 $\in E$ ，保证 $u, v$ 属于不同点集。

容易发现二分图中不存在奇环。（走偶数步才能回到某一点集）
二分图的匹配：选定一些边，这些边之间没有公共点。

建网络流模型即可，通过虚拟源点和虚拟汇点限制 $1$ 。

如果要输出方案，可以通过 $f (u, v) < c (u, v)$ 判断。如果根据残量网络，需要根据反向边的残量网络判断。

代码

3. 最大权闭合子图

分成正点和负点，把不选正点看作损失，每一种割对应一种方案代表不选。

答案即为正收益减去最小损失，即最小割，根据最小割最大流，即最大流。

具体可以看我之前的博客浅谈网络流。

4. 费用流

【模板】最小费用最大流

既然是最大流的前提上费用最小费用，用到的思想一定是基于 FF 增广思想上的。

SSP 算法

贪心，在每次增广中贪心的选择单位流量花费最小的增广路增广。考虑到负权，使用 SPFA 实现。

原图有负环时，最小费用不存在。若无负环，则图中不可能存在负环。

原因：考虑归纳法。

如果当前残量网络上无负环，则增广后同样无负环。若负环由原图上正环的反向边组成，由于找的是最短路，不可能经过原图上正环的所有边；若负环由一部分正向边一部分反向边组成，先遍历的一定是相对较短的，则形成的环非负。

时间复杂度 $O (nm f)$ ， $f$ 为最大流。

基于 EK 的实现代码

基于 Dinic 的实现代码

5. 上下界网络流

无源汇有上下界可行流

是否存在一种可行流使得每个点都满足流量平衡，对于边 $(u, v)$ ，有限制 $\le f(u,v) \le r(u,v)$ 。

设计 $f^{'} (u, v) = f (u, v) - l (u, v)$ ， $\le f'(u,v) \le r(u,v) - l(u,v)$ ，即一般的网络流模型。

此时 $f^{'}$ 关于点 $u$ 并不满足流量平衡。

根据 $f$ 的流量平衡可推出 $f^{'}$ 应该满足 $\sum_{x \to u} l(x,u)+\sum_{x \to u} f'(x,u) = \sum_{u \to y} l(u,y)+\sum_{u \to y} f'(u,y)$ 。

记虚拟源点为 $s$ ，虚拟汇点为 $t$ ，建 $s$ 到 $u$ 容量为 $\sum_{x \to u} l(x,u)$ 的边，建 $u$ 到 $t$ 容量为 $\sum_{u \to y} l(u,y)$ 的边。

跑最大流，有解当且仅当 $\sum f(s,u) = \sum_u (\sum_{x \to u} l(x,u))$ 。相当于问存不存在一种方案， $f (s, u)$ 都能达到容量限制，此时一定是最大流。如果最大流不能满足，那么一定无解.

求方案根据 $f^{'}$ 求 $f$ 即可。

代码

有源汇有上下界可行流

有源汇时，考虑到只有源点与汇点不满足流量平衡，由汇点向源点连一条 $[0,\inf]$ 的边，转为无源汇上下界可行流。

有源汇有上下界最大流

SOL1：二分最大流 $f$ ，由汇点向源点连一条 $[f,\inf]$ 的边，转为无源汇上下界可行流，时间复杂度 $O(n^2m \log V)$ 。

SOL2：找到一条可行流，在可行流的残量网络上跑 $S$ 到 $T$ 的最大流，两者相加。

题目

清理雪道

DAG 上的最小边覆盖问题。

本题题解

CF1783F Double Sort II

错排建图的套路。

先只考虑一个数列：记 $i$ 所在位置 $p_i$ ，将 $\to p_i$ 建边，形成若干个环，每次操作可以让环上少一个点，因此最小操作次数为 $n$ 减去环的数量。

如果从反面出发，想最多能保留几个点可以不动，省操作次数，能保留的数量就是环的数量。

考虑两个数列：对于一个环，最多被省一个点。对于一个点，最多被省一次。

按 $i$ 所在的两个环建边跑二分图最大匹配即可。

CF1766F MCF

最小费用有源汇可行流，但有一个流量与容量奇偶性相同的限制。

对于奇数边有下界 $\ge 1$ ，给他们制定下界，先让他们流入 $1$ 的容量。然后我们令 $\dfrac {f(u,v)} {2}，c'(u,v) =\dfrac {c(u,v)} {2}$ 。文章来源地址https://www.toymoban.com/news/detail-595867.html