最大流问题
最大流问题满足以下三个条件:
- 容量限制:(f(u,v)≤c(u,v))
- 斜对称性:(f(u,v)=-f(v,u))
- 流量平衡:(sum_ {(u,v)∈E}f(u,v)=0)(除(s),(t)外的图中任意两点)
原图中不存在的边也假设存在,视为容量为0.
残量网络:计算出每条边上容量(c)与流量(f)之差后所得到的图。由于上述的原因,边数可能是原图的两倍。对于原图中一条(c=16,f=11)的单向边,在残量网络中对应边权为(5(16-11))与(11(0-(-11)))的两条边。
增广路算法
当且仅当残量网络中不存在(s→t)的有向道路(增广路)时,此时的流是从(s)到(t)的最大流。
Edmonds-Karp算法
核心流程
- 对图进行(BFS),直到形成(s->t)的通路(即当找到(t)时),同时维护这条通路上的最小残量(minflow=e[i].cap-e[i].flow),并保存通路上每一个节点的入边。只要能到达(t),这条通路就是增广路,否则图中已经没有增广路。
- 形成通路之后,按照先前保留的各节点的入边,从终点(t)开始沿着通路倒退回去,并更新路上每一条边的正向边的流量
e[i].flow
与反向边的流量e[i^1].flow
。 - 整条通路的流量更新完毕后,更新答案(maxflow)。
- 重复以上步骤,直到图中没有增广路。
优化方法
- 重边处理。即将正向边(u→v)的多条管道合并为一条,只需将(cap)属性累加即可。而反向边不需要特殊处理。
(链式前向星+重边处理)
int n, m, s, t;
int num = 1;//让边的编号从2开始
int head[maxn], pre[maxn];
LL flow = 0;
LL d[maxn];
int flag[300][300];
//记录重边,重边的容量累加到一条边上
struct Edge {
int next, to;
LL cap;
LL flow;
}e[maxn*4];
void addedge(int from,int to,LL cap){
//存正向边
num++;
e[num].next = head[from];
e[num].to = to;
e[num].cap = cap;
e[num].flow = 0;
head[from] = num;
//存反向边
num++;
e[num].next = head[to];
e[num].to = from;
e[num].cap = 0;
e[num].flow = 0;
head[to] = num;
}
void update() {
//从终点开始退回去,沿路修改边权
//通路的最小值m即d[t]
for (int x = t; x != s; x = e[pre[x]^1].to) {
e[pre[x]].flow += d[t];
e[pre[x] ^ 1].flow -= d[t];
}
flow += d[t];
}
void ek(int s, int t) {
for (;;) {
mem(d, 0);
//d[i]记录s->i路径上的最小残量
//由于总是正数,可以同时起到记录是否访问过的作用
queue<int> q;
q.push(s);
d[s] = INF;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
if (!d[e[i].to] && e[i].cap > e[i].flow) {
pre[e[i].to] = i;
//记录e[[i].to是从哪条边过来的
d[e[i].to] = min(d[u], e[i].cap - e[i].flow);
q.push(e[i].to);
}
}
if (d[t]) break;
//已经访问过t,可以跳出了
}
if (!d[t]) break;
//整张图找遍依然到达不了t,说明已经没有增广路了
update();
}
}
int main() {
cin >> n >> m >> s >> t;
mem(flag, 0);
f(i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
if (!flag[u][v]) {
addedge(u, v, w);
flag[u][v] = num - 1;
//num是v->u的编号
//num-1才是u->v的编号
}
else e[flag[u][v]].cap += w;
//如果是重边,容量加到已存在的那条边上
}
ek(s,t);
cout << flow;
return 0;
}
Dinic算法
EK算法中,每一次BFS都只能找到一条增广路,效率不高。而Dinic算法则能通过BFS同时找到多条最短增广路,再通过DFS对找出的所有最短增广路同时增广。
核心流程
-
对图进行BFS,直到形成(s→ t)的通路(即找到终点(t))。同时用数组(d[i])记录每个节点(i)所在层级,这类似于经典BFS题目中常记录的步数。BFS的目的在于找到图中的最短增广路。其中最短定义为路上经过的节点数最少。联想到BFS的性质可以知道,当找到终点(t)时,找到的最短增广路有多条。
-
在BFS成功形成(s→ t)通路的基础上,从(s)开始进行DFS。搜索路径所经过的节点层级严格递增,以保证走的是最短增广路。同时维护路径上的最小残量(minflow)。当找到终点(t)时,带着整条通路上的最小残量(minflow)回溯,这相当于(EK)算法中“从终点开始倒退回去沿路更新”的操作。
- 在回溯过程中,同(EK)算法一样,会更新路上每一条边的正向边的流量
e[i].flow
与反向边的流量e[i^1].flow
。但还要更新额外的变量(nowflow),表示将当前节点(now)视为起点,以此出发后所经过的所有最短增广路的总流量。以及将当前节点(now)视为终点时的通路最小残量(minflow)。故前者加,后者减。 - 当节点(now)的各数据更新完毕后,带着以(now)为起点的总流量(nowflow)回溯。
- 在回溯过程中,同(EK)算法一样,会更新路上每一条边的正向边的流量
-
一次DFS最终得到的值,即以(s)为起点的多条最短增广路的总流量(nowflow),用它更新答案(maxflow)。
-
重复以上所有步骤,直到BFS找不到增广路。
优化方法
-
剪枝。注意到当前节点(now)的各数据更新是基于更深一层(DFS)回溯上来的值(k),当(k)为(0)时,它对节点的更新是无任何贡献的,所以可以把(k)的来源节点(v)从层级网络中剥离,即令
d[v]=INF
,这样之后的DFS就不会再访问以(v)为起点的最短增广路了。 -
当前弧优化。(这里的弧其实就是边)
对于一个节点(u),当它在DFS中走到了第(i)条弧时,前(i-1)条弧到汇点的流一定已经被流满而没有可行的路线了。那么当下一次再访问(u)节点的时候,前(i-1)条弧就可以被删掉而没有任何意义了。所以我们可以在每次枚举节点(now)所连的弧时,改变枚举的起点,这样就可以删除起点以前的所有弧以达到优化的效果。
typedef long long LL;
const long long INF = 2005020600;
const int maxn = 5e4 + 100;
int n, m, s, t;
int num = 1;//让边的编号从2开始
int head[maxn];
bool vis[maxn];
LL d[maxn], Maxflow;
int cur[maxn];
int flag[300][300];
int cnt[maxn];
//记录重边,重边的容量累加到一条边上
struct Edge {
int next, to;
LL cap;
LL flow;
}e[maxn*4];
void addedge(int from,int to,LL cap){
//存正向边
num++;
e[num].next = head[from];
e[num].to = to;
e[num].cap = cap;
e[num].flow = 0;
head[from] = num;
//存反向边
num++;
e[num].next = head[to];
e[num].to = from;
e[num].cap = 0;
e[num].flow = 0;
head[to] = num;
}
bool bfs() {
for (int i = 0; i <= n; i++) d[i] = INF;
queue<int>q;
q.push(s);
d[s] = 0;
cnt[s] = head[s];
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
if (d[e[i].to]==INF && e[i].cap > e[i].flow) {
d[e[i].to] = d[u] + 1;
cnt[e[i].to] = head[e[i].to];
q.push(e[i].to);
if (e[i].to == t) return true;
}
}
}
return false;
}
//bfs将整张图跑一遍,将所有点分层,这样就可以一次性找出s->t的所有最短增广路
//最短指经过最少的节点
//dfs 从s开始递归搜索残量网络,且递归路线是层级逐渐加深的,这样就能保证走的是最短路
//并且在递归过程中维护通路上的最小残量
LL dfs(int now, LL minflow) {
if (now == t) return minflow;
//minflow维护以now为终点的最小残量
LL nowflow = 0;
for (int i = cnt[now]; i && minflow; i = e[i].next) {
cnt[now] = i;
//当前弧优化
if (d[e[i].to] == d[now] + 1 && e[i].cap > e[i].flow) {
LL k = dfs(e[i].to, min(e[i].cap - e[i].flow, minflow));
if (!k) d[e[i].to] = INF;
//剪枝
e[i].flow += k;
e[i ^ 1].flow -= k;
nowflow += k;
minflow -= k;
//因为通路上的所有路径的残量都少了k
//所以以now为终点的所有路径的最小残量也要减k
}
}
return nowflow;
}
void dinic(){
while (bfs()) {
Maxflow += dfs(s, INF);
}
}
int main() {
cin >> n >> m >> s >> t;
f(i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, w);
}
dinic();
cout << Maxflow;
return 0;
}
注意:通常(cap)和(flow)这两个属性可以简化为一个属性(val),意为边(i)的残量
这样做的话,在增广处理时,(正向边.val-流量),(反向边.val+流量)