流网络
对于一个有向图
在这个有向图中,存在
我们把这样的图称之为网络。
可行流
我们定义可行流函数
,任意一条边的流量不超过这条边的容量。 ,即任意一个点,进入这个点的流量都等于出去的流量。
一个网络的流就是源点发出的全部流量,记
残留网络
残留网络的点集和边集与原网络是一样的,但唯一不同的是每条边存在一个剩余容量,这里我们对于一个有向边,考虑其的反向边:
- 当
, 。
反向边的加入是为了存在反悔贪心的操作,保证了算法正确性,在程序中我们所建的都是残留网络。
增广路
对于一条从
那么如果有了一条增广路,我们就会尝试让源点分一点流量给这条增广路,而分配的流量就是每条边剩余容量的最小值(显然多了也流不过去),不难发现,当网络中存在增广路,则最大流答案将变大。
割
如果有网络
割的容量
对于一个割
最小割
最小割的指的是割的最小容量。
割的流量
对于一个割
意思为从
割的性质
。即任意的一个割与原网络的任意一个可行流,有割的流量不超过割的容量。 ,即割的流量等于原网络的可行流。证明:
(性质 )且 (性质 )又
(性质 )记
, 中不存在源点和汇点,则流量守恒,有 ,由性质 可得。则我们能得到最大流不超过最小割。
最大流
对于一个在网络的所有可行流,所得到的最大的
最大流指的是最大可行流。
*最大流最小割定理
最大流最小割定理指的是这样
证明:
若当原网络取到最大流
时,残留网络仍存在增广路。 那么我可以通过增广这条增广路的方式增加原网络流量使其不是最大流。
证毕。
由于只需存在一个割满足,那么考虑一种构造方式:
对于当前的残留网络,
集合为源点 通过剩余容量不为 的边可到达的点集, 为 。 由于
条件,所以 集合一定不包含 。 考虑此时的
。
,我们有 。如果 ,那么在残留网络中这条边的剩余流量 ,则 应该也在 中矛盾。
,我们有 ,证明方式同上。 那么我们有
又有
, ,证毕。
原命题
由性质
,最大流小于等于最小割。 最小割
所以最小割小于等于最大流,所以最小割等于最大流,同时得到
就是最大流。 证毕。
那么我们就得到了,残留网络中没有增广路和当前的流是最大流是充要条件。
最大流算法
网络最大流是怎么求的呢?有了对于增广路的概念,我们不难想到一个较为朴素的做法:在当前残留网络中,找到一条增广路,如果能找到增广路,说明当前的流的答案会变大,增加流,然后把增广路上的每条边的容量减掉增广路上所有边的最小容量,重复过程直到不能找到增广路。
乍一看十分之正确,但是存在一个问题:对于这样的一个贪心模拟的过程是否存在着后效性?
答案是有可能的,比如有
问题的本质是存在后效性,那么能不能想办法采用类似反悔贪心的做法来做?
考虑为每条边开一个反向边。初始时反向边容量设为
在我们增广了一次之后,将增广的路径上的正向边减少容量,反向边增加容量,这样上面的情况就会被反悔出来。
由于最大流最小割定理,所以只要残留网络中没有增广路,则一定得到最大流。
实现十分的容易,就是扫整张网络找增广路,并修改路径上的容量。
时间复杂度
理论证明的复杂度为
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 20005, Inf = 0x3f3f3f3f;
int n, m, S, T;
int flow;
int head[N], e[M], f[M], nxt[M], top;
int que[N], incf[N], pre[N];
bool vis[N];
void add(int a, int b, int c) {
e[top] = b, f[top] = c, nxt[top] = head[a], head[a] = top++;
e[top] = a, f[top] = 0, nxt[top] = head[b], head[b] = top++;
}
bool bfs() {
int hh = 0, tt = 1;
memset(vis, false, sizeof vis);
memset(incf, 0, sizeof incf);
que[hh] = S, vis[S] = true, incf[S] = Inf;
while(hh != tt) {
int u = que[hh++];
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(vis[v] == false && f[i] > 0) {
vis[v] = true;
pre[v] = i;
incf[v] = min(incf[u], f[i]);
que[tt++] = v;
}
}
}
return incf[T] > 0;
}
void EdmondsKarp() {
while(bfs() == true) {
int t = incf[T];
flow += t;
for(int u = T; u != S; u = e[pre[u] ^ 1]) {
f[pre[u]] -= t, f[pre[u] ^ 1] += t;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> S >> T;
memset(head, -1, sizeof head);
while(m--) {
int u, v, c;
cin >> u >> v >> c;
add(u, v, c);
}
EdmondsKarp();
cout << flow << '\n';
cout.flush();
return 0;
}
那么我们就要用 dfs()
找增广路了,但在找增广路前,首先需要用 bfs()
做一些准备工作,具体就是标注 要不然跑就不用跑那么多遍。
这样我们实际是给网络标了一个 DAG 序,使 dfs()
不会进入死循环,而其特有的回溯功能可使我们遍历到多条增广路。
那么算法流程是:先用 bfs()
分层,然后 dfs(u, Flow)
表示走到了
优化
一个剪枝,搜的时候记录当前点的流出量
优化
一个剪枝,叫做当前弧优化。
当我们在枚举
当
当
当
每次都重新跑了所有出边,但由于 dfs()
的性质可能在前面被枚举到的出边容量已经增广完了。
所以记录
十分有用的优化。
优化
对于一条边
时间复杂度
理论证明的复杂度为
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 200005, Inf = 0x3f3f3f3f;
int n, m, S, T;
int flow;
int head[N], e[M], f[M], nxt[M], top;
int que[N], dep[N], cur[N];
void add(int a, int b, int c) {
e[top] = b, f[top] = c, nxt[top] = head[a], head[a] = top++;
e[top] = a, f[top] = 0, nxt[top] = head[b], head[b] = top++;
}
bool bfs() {
int hh = 0, tt = 1;
memcpy(cur, head, sizeof cur);
memset(dep, 0x3f, sizeof dep);
que[hh] = S, dep[S] = 0;
while(hh != tt) {
int u = que[hh++];
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(dep[v] == Inf && f[i] > 0) {
dep[v] = dep[u] + 1;
que[tt++] = v;
}
}
}
return (dep[T] != Inf);
}
int dfs(int u, int flow) {
if(u == T) {
return flow;
}
int used = 0;
for(int i = cur[u]; ~i; i = nxt[i]) {
cur[u] = i;
int v = e[i];
if(dep[v] == dep[u] + 1 && f[i] > 0) {
int low = dfs(v, min(f[i], flow - used));
if(low > 0) {
used += low, f[i] -= low, f[i ^ 1] += low;
if(used == flow) break;
}
else {
dep[v] = Inf;
}
}
}
return used;
}
void Dinic() {
while(bfs() == true) {
flow += dfs(S, Inf);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> S >> T;
memset(head, -1, sizeof head);
while(m--) {
int u, v, c;
cin >> u >> v >> c;
add(u, v, c);
}
Dinic();
cout << flow << '\n';
cout.flush();
return 0;
}
最大流相关模型和例题
二分图匹配
二分图匹配一般指的是存在两个点集,点集内部没有边,点集之间有若干条边相连,一个匹配指的是从边集中选出一个子集,使得一个点至多出现在一条边中。
我们将其抽象成一个网络流模型,对于每一条边
P2756 飞行员配对方案问题
最典型的二分图匹配,我们向源点和每一个外籍飞行员连一条容量为
我们需要先证明原问题的每一个可行解
对于一个可行解
对于一个可行流
因为满足流量守恒,所以除了源点和汇点外,每个点的流入的流量和流出的流量相等,外国籍点流入流量和英国记流出流量均最多为
所以现在我们证明了每个可行解
这个证明比较简单:因为
代码:https://www.luogu.com.cn/record/101009585
P3254 圆桌问题
在这道题中,区别仅仅在于从每个点的容量限制的不同,因为一个单位有
代码:https://www.luogu.com.cn/record/101009737
无源汇上下界可行流
给定一个无源点和汇点的网络,每条边要求的流量存在上下界,求这个网络是否存在可行流。
因为没有源点和汇点,所以一个可行流需要保证所有的点满足流量守恒。
如果本题在没有下界的情况下,在初始什么流量也没有的时候,所有点均满足流量守恒,但如果我们先给所有边流下界的流量,并不能保证所有点流量守恒,那么我们为了满足流量守恒,我们可以记录
我们不妨设原图为
那么对于一个原图可行流
什么意思?就是在原图中有的那些边的流量,我们在新图中将它们的流量设为流量减下界,那么在新图中新增的边为每个点到虚拟源点/虚拟汇点的边,那么
而由于
对于一个新图可行流
这当然也是十分好说的,对于图
LOJ#115. 无源汇有上下界可行流
最终流程:求
struct NetWork {
int ver, limit, capacity, nxt; // 注意可能会需要多记一个 limit
void ins(int u, int v, int l, int w) {
ver = v, limit = l, capacity = w, nxt = head[u];
head[u] = top;
}
}Net[20805];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
s = 0, t = n + 1;
for(int i = 1;i <= m;i++) {
int u, v, l, w;
cin >> u >> v >> l >> w;
Net[++top].ins(u, v, l, w - l);
Net[++top].ins(v, u, l, 0);
A[u] -= l, A[v] += l; // 求 A[i]
}
for(int i = 1;i <= n;i++) {
if(A[i] > 0) { // 流入的下界流量之和大于流出的下界流量之和,建 s -> i 的边。
Net[++top].ins(s, i, 0, A[i]);
Net[++top].ins(i, s, 0, 0);
sum += A[i]; // 注意求一下满流大小。
}
else { // 反之建 i -> t 的边。
Net[++top].ins(i, t, 0, -A[i]);
Net[++top].ins(t, i, 0, 0);
}
}
Dinic();
if(Flow != sum) {
cout << "NO\n";
}
else {
cout << "YES\n";
for(int i = 2;i <= 2 * m;i += 2) { // 在输出原网络流的方案时,流量 = 新网络流量 + 边的流量下界。
cout << Net[i ^ 1].capacity + Net[i].limit << '\n';
}
}
cout.flush();
return 0;
}
有源汇上下界可行流
有了源点和汇点之后,说明有两个点的流量守恒就不用满足了,那么考虑怎么转化为无源汇上下界可行流。
这里一个比较巧妙的操作是连
有源汇上下界最小/大流
一个十分复杂的题目(指证明)
我们可以轻易的求一个可行流,但是如何找到最小或最大流呢,做法十分之简单:按有源汇上下界可行流跑虚拟源点到虚拟汇点的最大流,然后把
下面我们来证明一下。
我们设原图为
那么我们首先观察
那么接下来我们观察任意两个
考虑到两个满流都保证了虚拟源点流出的流量和虚拟汇点流入的流量是满的,那么相减之后这些有关虚拟源点和虚拟汇点的边的流量均变为了
那么我们看这个是否对应一个残留网络的可行流
所以综上,我们证明了:残留网络
LOJ#116. 有源汇有上下界最大流
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> s >> t;
S = 0, T = n + 1;
for(int i = 1;i <= m;i++) {
int u, v, l, w;
cin >> u >> v >> l >> w;
Net[++top].ins(u, v, w - l);
Net[++top].ins(v, u, 0);
A[u] -= l, A[v] += l;
}
for(int i = 1;i <= n;i++) {
if(A[i] > 0) {
Net[++top].ins(S, i, A[i]);
Net[++top].ins(i, S, 0);
sum += A[i];
}
else {
Net[++top].ins(i, T, -A[i]);
Net[++top].ins(T, i, 0);
}
}
Net[++top].ins(t, s, I);
Net[++top].ins(s, t, 0);
Dinic();
if(Flow < sum) {
cout << "please go home to sleep\n";
}
else {
int res = Net[top].capacity;
Net[top].capacity = Net[top - 1].capacity = 0;
S = s, T = t;
Flow = 0;
Dinic();
cout << res + Flow << '\n';
}
cout.flush();
return 0;
}
使用最大流作为判定的问题
POJ#2455. Secret Milking Machine
求最长道路的最小可能长度,不难想到二分答案
将所有能用的边的流量设为
代码:http://poj.org/showsource?solution_id=23967440
P2754 [CTSC1999] 家园 / 星际转移问题
不难发现此题也有单调性,如果
那么考虑如何判定,则我们需要将问题转化为一张流网络。本题采用了对每一天分层的思想建图,我们分几类边说明。
我们令地球编号为
- 由于全部的人一开始都在地球,我们连一条
,容量为 的边,代表人从地球出发。 - 由于每个人可在他当前的太空站停留到下一天且没有人数的限制,我们连一条
,容量为 的边,表示停留的情况。 - 如果一些人在某一天已经到达了
号点,代表已经到达了终点,我们连一条 ,容量为 的边,表示已经到达终点。 - 最后是有关太空船的连边,对于每一天,我们需要计算出每个船昨天停靠的太空站
与今天停靠的太空船 ,且太空站有人数限制 ,那么连 ,容量为 的边,代表太空船运输的情况。
这样我们就建好了整张图,可以发现这张图是与原问题等价的,那么我们每次往后加一天的边和点,跑最大流判断流量是否大于等于需要运输的人数
那么什么情况下无解?考虑如果有合法解当且仅当
代码:https://www.luogu.com.cn/record/101010280
拆点最大流问题
在前面的问题中,我们了解到如果某条边有限制,那么直接修改这条边的容量就行,那么点上有限制该怎么做呢。我们可以考虑将一个点拆为入点和出点,之间用对应容量的边连接。
P2891 [USACO07OPEN]Dining G
本题类似于一个二分图匹配,我们需要对每个奶牛各匹配两个物品,那么按之前的建图方式建图,源点向食品连边,食品向奶牛连边,奶牛向饮料连边,饮料向汇点连边就完成转化?
简单思考可知两者并不等价,因为没有限制一个奶牛只能拿一个食品和一个饮料,所以我们需要添加这个限制,我们将奶牛拆成两个点,一个连食品,一个连饮料,最终在这两个点之间连一条容量为
代码:https://www.luogu.com.cn/record/101026249
P2766 最长不下降子序列问题
首先我们设
然后考虑如何去最多的数量。观察到对于一个长为
当能使用多次
注意当
代码:https://www.luogu.com.cn/record/101026610
POJ#3498. March of the Penguins
我们分步骤将原问题转化为一个等价的流网络:
- 一开始有一些企鹅在某些浮冰上:将源点向这些浮冰连容量为企鹅数量的边。
- 每个浮冰的起跳次数有限制:相当于对每个点的限制,将其拆为入点和出点,并连一条容量为跳跃次数的边。
- 距离小于等于
的浮冰可以到达:枚举任意两个浮冰,看距离是否小于等于 ,然后向浮冰的出点向下一块的浮冰的入点连一条容量为 的边。 - 找出所有可以汇合的浮冰:我们可以枚举一个点作为汇点,跑最大流看是否等于企鹅数量。
代码:http://poj.org/showsource?solution_id=23967744
最大流建图实战
SP4063 MPIGS - Sell Pigs
我们考虑如果某个猪舍从未被打开过,那么第一个打开这个猪舍的顾客相当于有了第一次的购买权,而后打开的顾客可理解为是在买前几次顾客买剩下的猪。由于前几个顾客购买后拥有调整猪舍的权利,打开的猪舍相当于也可能会被新顾客购买,尽管新顾客可能不能打开某个猪圈。
这提示我们采用一种建图方式体现顾客之间的购买和调整的先后顺序。
因此我们按如下方式建边:
- 如果某个顾客第一次打开一个猪舍,源点
向这个猪舍连容量为此猪舍猪的数量大小的边。 - 如果某个顾客不是第一次打开一个猪舍,那么让上一个打开这个猪舍的顾客向这个顾客连边,容量为
。 - 每个顾客向汇点
连容量为顾客需求猪的数量大小的边。
这样的思路正确性在于:保证了每个顾客在购买时打开的猪圈一定是在上一次顾客购买之后的,上一次顾客购买后的调整就相当于是顾客之间的连边。
最后我们跑最大流即为答案。
代码:https://www.luogu.com.cn/record/101030821
最小割算法
由于最小割等于最大流,所以我们直接使用
顺便说明一个最小割构造方式,由最大流最小割定理的证明过程,当我们求出一个可行流后,沿着所有剩余容量大于
代码略。
最小割相关模型和例题
最小割直接应用
AcWing2279. 网络战争
对于平均最小边权,不难想到 01 分数规划的做法。
二分一个值
移项后得
注意精度问题。
#include <bits/stdc++.h>
using namespace std;
typedef long double lf;
const int N = 105, M = 805, Inf = 0x3f3f3f3f;
const lf eps = 1e-4;
int n, m, S, T;
lf flow;
int head[N], e[M], w[M], nxt[M], top;
int que[N], dep[N], cur[N];
lf f[M];
void add(int a, int b, int c) {
e[top] = b, w[top] = c, nxt[top] = head[a], head[a] = top++;
e[top] = a, w[top] = c, nxt[top] = head[b], head[b] = top++;
}
bool bfs() {
int hh = 0, tt = 1;
memcpy(cur, head, sizeof cur);
memset(dep, 0x3f, sizeof dep);
que[hh] = S, dep[S] = 0;
while(hh != tt) {
int u = que[hh++];
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(dep[v] == Inf && f[i] > 0) {
dep[v] = dep[u] + 1;
que[tt++] = v;
}
}
}
return (dep[T] != Inf);
}
lf dfs(int u, lf flow) {
if(u == T) {
return flow;
}
lf used = 0;
for(int i = cur[u]; ~i; i = nxt[i]) {
cur[u] = i;
int v = e[i];
if(dep[v] == dep[u] + 1 && f[i] > 0) {
lf low = dfs(v, min(f[i], flow - used));
if(low > 0) {
used += low, f[i] -= low, f[i ^ 1] += low;
if(used == flow) break;
}
else {
dep[v] = Inf;
}
}
}
return used;
}
void Dinic() {
while(bfs() == true) {
flow += dfs(S, Inf);
}
}
bool chk(lf mid) {
flow = 0;
for(int i = 0; i < top; i += 2) {
if(w[i] <= mid) {
flow += w[i] - mid;
f[i] = f[i ^ 1] = 0;
}
else {
f[i] = f[i ^ 1] = w[i] - mid;
}
}
Dinic();
return flow <= 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> S >> T;
memset(head, -1, sizeof head);
for(int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
}
lf l = 0, r = 1e7, mid, ans;
while(r - l > eps) {
mid = (l + r) / 2;
if(chk(mid) == true) {
r = mid, ans = mid;
}
else {
l = mid;
}
}
cout << fixed << setprecision(2) << ans << '\n';
cout.flush();
return 0;
}
AcWing2280. 最优标号
看到求异或值最大,不难想到拆位求的思路。
把每一位抠出来后,每个点的编号都只能是
那如何把
考虑到我们如果将割
注意一些点可能已经被设权值,要提前先加入
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505, M = 7005, Inf = 0x3f3f3f3f;
int n, m, S, T;
pair<int, int> edge[M];
int a[N];
ll flow;
int head[N], e[M], f[M], nxt[M], top;
int que[N], dep[N], cur[N];
void add(int a, int b, int c) {
e[top] = b, f[top] = c, nxt[top] = head[a], head[a] = top++;
e[top] = a, f[top] = 0, nxt[top] = head[b], head[b] = top++;
}
bool bfs() {
int hh = 0, tt = 1;
memcpy(cur, head, sizeof cur);
memset(dep, 0x3f, sizeof dep);
que[hh] = S, dep[S] = 0;
while(hh != tt) {
int u = que[hh++];
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(dep[v] == Inf && f[i] > 0) {
dep[v] = dep[u] + 1;
que[tt++] = v;
}
}
}
return (dep[T] != Inf);
}
int dfs(int u, int flow) {
if(u == T) {
return flow;
}
int used = 0;
for(int i = cur[u]; ~i; i = nxt[i]) {
cur[u] = i;
int v = e[i];
if(dep[v] == dep[u] + 1 && f[i] > 0) {
int low = dfs(v, min(f[i], flow - used));
if(low > 0) {
used += low, f[i] -= low, f[i ^ 1] += low;
if(used == flow) break;
}
else {
dep[v] = Inf;
}
}
}
return used;
}
void build(int j) {
memset(head, -1, sizeof head); top = 0;
for(int i = 1; i <= m; ++i) {
int u = edge[i].first, v = edge[i].second;
e[top] = v, f[top] = 1, nxt[top] = head[u], head[u] = top++;
e[top] = u, f[top] = 1, nxt[top] = head[v], head[v] = top++;
}
for(int i = 1; i <= n; ++i) {
if(a[i] >= 0) {
if(1 << j & a[i]) {
add(i, T, Inf);
}
else {
add(S, i, Inf);
}
}
}
}
void Dinic(int j) {
build(j);
while(bfs() == true) {
flow += (ll)dfs(S, Inf) << j;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
S = 0, T = n + 1;
memset(a, -1, sizeof a);
for(int i = 1; i <= m; ++i) {
cin >> edge[i].first >> edge[i].second;
}
int k;
cin >> k;
while(k--) {
int u, p;
cin >> u >> p;
a[u] = p;
}
for(int j = 0; j < 31; ++j) {
Dinic(j);
}
cout << flow << '\n';
cout.flush();
return 0;
}
最大权闭合图
对于一张图
一个闭合图指从图中选出一些点构成集合
一个闭合图的权是闭合图点集中的点权之和。
最大权闭合图就是所有闭合图中权值最大的那个。
这个问题与最小割有什么联系?我们先说网络建法:对于图中的原先的边,在网络中添加容量为
最大权闭合图
我们定义一个特殊的割叫做简单割,表示所有的割边都跟源点和汇点相连。那么按上述方式建的网络的最小割是不是简单割呢,由最大流最小割定理,最小割等于最大流,而最大流是有限的,则割边不可能包括中间容量为
接下来我们要证明闭合图与简单割一一对应。对于一个闭合子图,记它的点集为
那么对于一个简单割
那么闭合图的权到底和这个简单割的容量的有什么关系?
设
,虚拟源点到虚拟汇点没有直接的边,没有贡献。 ,由于是简单割,所以没有贡献。 ,每条割边的容量对应割中的那些正权点的权值,所以这块贡献为正权点权值之和。 ,每条割边的容量对应割中的那些负权点的权值,所以这块贡献为负权点权值之和。
所以最后写成式子就是:
我们去看
则
至此完成证明。
[NOI2006] 最大获利
本题中如果把建设中转站的费用看作负权点,用户收益看作正权点的话,我们可以转化为最大权闭合图问题。
我们只需向每个用户群和对应的两个中转站连边,当且仅当两个中转站都选了,这个用户群才能选,所以从每个用户群出发得保证走到两个中转站,所以是个闭合子图。
代码:https://www.luogu.com.cn/record/101110660
最大密度子图
对于一个点集
看到除法,我们使用 01 分数规划,判定
我们把系数提到前面得到
于是有了如下的建图:从源点向每个点连容量为
我们还是分类算割的容量:
,没有,无贡献。 ,每条的容量为 。 ,每条的容量为 。 ,每条的容量均为 。
这样我们只需最小化
最小点权覆盖集
最小点权覆盖集指的是对于一个图
在一般图中,最小点权覆盖集中是 NP-完全问题,但在二分图中,我们可以使用最小割来求解,因此下列所用算法仅适用于二分图。
最小点权覆盖集.png
我们对于一个二分图,而如下方式建出网络,由于最小割求的是割边容量的最小值,而最小点权覆盖集对应的是点权值最小,那么我们希望将割边限定在
最大点权独立集
最大点权独立集是最小点权覆盖集的对偶问题,当每个点的权值均为
而当权值不为
证明从双方向证明:
- 若
是点覆盖集,那么 是独立集。 - 若
是独立集,那么 是点覆盖集。
用反证法可以轻易的证明出来,因此沿用最小点权覆盖集的方法做即可。
P4474 王者之剑
这题我们先从性质出发:
- 只能在偶数秒捡宝石。我们只需证奇数秒时所在的格子一定没有宝石即可,如果上一秒动了,那么在上一秒时此格子已经被清空,而如果上一秒原地不动,那么此时的宝石应该已经在上一秒被拿走,无论什么情况,奇数秒所在的格子没有宝石,因此只能在偶数秒捡宝石。
- 相邻的格子不可能同时拿到。显然易证。
根据这
代码:https://www.luogu.com.cn/record/101111765
费用流算法
费用流的定义其实非常简单,我们在每条边上添加了一个费用
在求最大流中,我们使用 bfs()
来找到一条增广路增广,由最大流最小割定理,这个算法是正确的,而对于最小费用最大流,我们只需将 bfs()
换成 spfa()
,每次找的是残留网络的最短费用路,然后用这条路增广即可。
注意图中不能出现负环,出现负环请参考P7173 【模板】有负圈的费用流。
时间复杂度
还是
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 100005, Inf = 0x3f3f3f3f;
int n, m, S, T;
int flow, cost;
int head[N], e[M], f[M], w[M], nxt[M], top;
int que[N], dis[N], pre[N], incf[N];
bool inque[N];
void add(int a, int b, int c, int d) {
e[top] = b, f[top] = c, w[top] = d, nxt[top] = head[a], head[a] = top++;
e[top] = a, f[top] = 0, w[top] = -d, nxt[top] = head[b], head[b] = top++;
}
bool spfa() {
int hh = 0, tt = 1;
memset(dis, 0x3f, sizeof dis);
memset(incf, 0, sizeof incf);
que[hh] = S, dis[S] = 0, incf[S] = Inf;
while(hh != tt) {
int u = que[hh++];
if(hh == N) hh = 0;
inque[u] = false;
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(dis[v] > dis[u] + w[i] && f[i] > 0) {
dis[v] = dis[u] + w[i];
pre[v] = i;
incf[v] = min(incf[u], f[i]);
if(inque[v] == false) {
que[tt++] = v;
if(tt == N) tt = 0;
inque[v] = true;
}
}
}
}
return incf[T] > 0;
}
void EdmondsKarp() {
while(spfa() == true) {
int t = incf[T];
flow += t, cost += t * dis[T];
for(int u = T; u != S; u = e[pre[u] ^ 1]) {
f[pre[u]] -= t, f[pre[u] ^ 1] += t;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> S >> T;
memset(head, -1, sizeof head);
for(int i = 1; i <= m; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
}
EdmondsKarp();
cout << flow << ' ' << cost << '\n';
cout.flush();
return 0;
}
在 spfa()
后多路增广,复杂度仍为
感觉没啥用就不写了。
费用流相关模型和例题
直接运用
P4015 运输问题
对于每个仓库
最后,向仓库
对于求最大费用最大流,可以将所有边的权值取相反数,求最小费用最大流后将所求费用再求相反数即可。
代码:https://www.luogu.com.cn/record/101131411
P4016 负载平衡问题
首先根据贪心,必定是将高于平均的仓库中货物转到低于平均的仓库。
那么我们从源点
最后在相邻两个仓库之间连容量
代码:https://www.luogu.com.cn/record/101131507
二分图最优匹配
P4014 分配问题
跟P4015 运输问题差不多,把源点和汇点的边容量都改为
代码:https://www.luogu.com.cn/record/101131608
费用流之最大权不相交路径
P4013 数字梯形问题
针对于路径不相交,我们只需将对应的路径容量设为
针对于点不相交,我们想到了在最大流学到的拆点技巧,将其分为入点和出点,在入点和出点连一条容量为
从不相交改到相交时,注意将相应边的容量放开即可。
代码:https://www.luogu.com.cn/record/101131742
网格图模型
AcWing382. K取方格数
本题中唯一一个难点:“若多条路线重复经过一个格子,只取一次”。也就是说,我们既要保证这个格子能被走多次,还要保证这个格子又一次代价能被计算到。
那么我们可以将格子拆点,从入点向出点连两条边,一条容量为
最后我们总结一些建图方式对应的意义:
- 连一条容量为
的边:某条边可以重复经过。 - 连一条容量为
的边:某条边仅能经过 次。 - 入点向出点连一条容量为
的边:某个点仅能经过 次。 - 入点向出点连一条容量为
,费用为 的边:某个点可经过任意次,且每次经过均有价值 。 - 入点向出点连一条容量为
,费用为 的边:某个点只有 次价值 且仅能经过 次。 - 入点向出点连一条容量为
,费用为 的边,和一条容量为 ,费用为 的边:某个点可经过任意次,只计算 次价值。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 20005, Inf = 0x3f3f3f3f;
int n, k, S, T;
int cost;
int head[N], e[M], f[M], w[M], nxt[M], top;
int que[N], dis[N], pre[N], incf[N];
bool inque[N];
void add(int a, int b, int c, int d) {
e[top] = b, f[top] = c, w[top] = d, nxt[top] = head[a], head[a] = top++;
e[top] = a, f[top] = 0, w[top] = -d, nxt[top] = head[b], head[b] = top++;
}
bool spfa() {
int hh = 0, tt = 1;
memset(dis, -0x3f, sizeof dis);
memset(incf, 0, sizeof incf);
que[hh] = S, dis[S] = 0, incf[S] = Inf;
while(hh != tt) {
int u = que[hh++];
if(hh == N) hh = 0;
inque[u] = false;
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(dis[v] < dis[u] + w[i] && f[i] > 0) {
dis[v] = dis[u] + w[i];
pre[v] = i;
incf[v] = min(incf[u], f[i]);
if(inque[v] == false) {
que[tt++] = v;
if(tt == N) tt = 0;
inque[v] = true;
}
}
}
}
return incf[T] > 0;
}
void EdmondsKarp() {
while(spfa() == true) {
int t = incf[T];
cost += t * dis[T];
for(int u = T; u != S; u = e[pre[u] ^ 1]) {
f[pre[u]] -= t, f[pre[u] ^ 1] += t;
}
}
}
inline int get(int x, int y) {
return (x - 1) * n + y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> k;
memset(head, -1, sizeof head);
S = 0, T = 1;
add(S, get(1, 1) * 2, k, 0);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
int c;
cin >> c;
add(get(i, j) * 2, get(i, j) * 2 + 1, 1, c);
add(get(i, j) * 2, get(i, j) * 2 + 1, Inf, 0);
if(i + 1 <= n) add(get(i, j) * 2 + 1, get(i + 1, j) * 2, Inf, 0);
if(j + 1 <= n) add(get(i, j) * 2 + 1, get(i, j + 1) * 2, Inf, 0);
}
}
add(get(n, n) * 2 + 1, T, k, 0);
EdmondsKarp();
cout << cost << '\n';
cout.flush();
return 0;
}
AcWing2195. 深海机器人问题
我们考虑对于每个初始有机器人的格子作为出发点连源点
#include <bits/stdc++.h>
using namespace std;
const int N = 270, M = 2000, Inf = 0x3f3f3f3f;
int a, b, n, m, S, T;
int cost;
int head[N], e[M], f[M], w[M], nxt[M], top;
int que[N], dis[N], pre[N], incf[N];
bool inque[N];
void add(int a, int b, int c, int d) {
e[top] = b, f[top] = c, w[top] = d, nxt[top] = head[a], head[a] = top++;
e[top] = a, f[top] = 0, w[top] = -d, nxt[top] = head[b], head[b] = top++;
}
bool spfa() {
int hh = 0, tt = 1;
memset(dis, -0x3f, sizeof dis);
memset(incf, 0, sizeof incf);
que[hh] = S, dis[S] = 0, incf[S] = Inf;
while(hh != tt) {
int u = que[hh++];
if(hh == N) hh = 0;
inque[u] = false;
for(int i = head[u]; ~i; i = nxt[i]) {
int v = e[i];
if(dis[v] < dis[u] + w[i] && f[i] > 0) {
dis[v] = dis[u] + w[i];
pre[v] = i;
incf[v] = min(incf[u], f[i]);
if(inque[v] == false) {
que[tt++] = v;
if(tt == N) tt = 0;
inque[v] = true;
}
}
}
}
return incf[T] > 0;
}
void EdmondsKarp() {
while(spfa() == true) {
int t = incf[T];
cost += t * dis[T];
for(int u = T; u != S; u = e[pre[u] ^ 1]) {
f[pre[u]] -= t, f[pre[u] ^ 1] += t;
}
}
}
inline int get(int x, int y) {
return x * (m + 1) + y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> a >> b >> n >> m;
memset(head, -1, sizeof head);
S = (n + 1) * (m + 1) + 1, T = (n + 1) * (m + 1) + 2;
for(int i = 0; i < n + 1; ++i) {
for(int j = 0; j < m; ++j) {
int c;
cin >> c;
add(get(i, j), get(i, j + 1), 1, c);
add(get(i, j), get(i, j + 1), Inf, 0);
}
}
for(int j = 0; j < m + 1; ++j) {
for(int i = 0; i < n; ++i) {
int c;
cin >> c;
add(get(i, j), get(i + 1, j), 1, c);
add(get(i, j), get(i + 1, j), Inf, 0);
}
}
for(int i = 1; i <= a; ++i) {
int k, x, y;
cin >> k >> x >> y;
add(S, get(x, y), k, 0);
}
for(int i = 1; i <= b; ++i) {
int r, x, y;
cin >> r >> x >> y;
add(get(x, y), T, r, 0);
}
EdmondsKarp();
cout << cost << '\n';
cout.flush();
return 0;
}
拆点
P1251 餐巾计划问题
本题中要注意我们将每一天的餐巾拆分为“用完的旧餐巾”和“需要的新餐巾”,然后我们对于“需要的新餐巾”向汇点连容量
而其余的不同情况的连边,参考下图。

餐巾计划问题.png
代码:https://www.luogu.com.cn/record/101132505
无源汇有上下界最小费用可行流问题
P3980 [NOI2008] 志愿者招募
我们先按如下方式建出网络:
志愿者招募.png
其中第
红色的边是指每类志愿者的工作区间
那么我们说每条边的容量均有下界值,因为如果小于下界,那么下一天的志愿者人数就不能满足要求。这是一个无源汇有上下界最小费用可行流问题,如何求解?
参考无源汇有上下界可行流的做法,我们对于每个点,统计进入这个点的容量
对按这种方式建成的新网络求最小费用最大流就是原问题的答案。
v1.5.1