网络流
前言
该 \(blog\) 无基本概念,配合网络流基本介绍共同食用为佳,也无复杂度及其证明,毕竟网络流是基本跑不到复杂度上限的
最大流
一种常见的网络流模型,
通常是求源点到汇点的最大流量,
在算法竞赛中通常使用 \(dinic\) 算法或者 \(ISAP\) 算法.
\(dinic\)
\(dinic\) 算法是基于 \(EK\) 算法的,
这里不多赘述(毕竟 \(EK\) 还是比较简单的而且又不用bushi).
(其实会在下面费用流的时候介绍)
我们每次从 \(s\) (源点)开始 \(BFS\) 寻找增广路(学过二分图最大匹配的童鞋应该都知道),
如果到了 \(t\) (汇点)就结束,
也就是说我们的 \(s\) 和 \(t\) 是连通的,
也就是存在增广路,
完了?
完了.WTF?
这就是 \(dinic\) 算法的基础——增广路算法(也就是 \(EK\) ).
我们可以发现这样每次只能增广一条路,
所以会很慢.
而 \(dinic\) 算法则是多路增广,
我们每次跑一遍 \(BFS\) 来构建一个叫做"分层图"的东西,
这里我们定义一个数组 \(d\)
\(d_i\) 代表到 \(i\) 节点的最短距离,
如果有一条边连接了节点 \(x\) 和节点 \(y\) ,
并且 \(d_x + 1 == d_y\) ,
这是不是意味着我们在 \(BFS\) 的时候是从 \(x\) 走到的 \(y\) ?
也就是说这条边(指连接 \(x\) 和 \(y\) 的这条边)可能存在于某一条增广路,
基于分层图的概念,
我们可以对上面的增广路算法进行一波优化,
于是乎便有了下面的代码⬇️(按照代码运行顺序阅读为佳哟)
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1205, maxm = 120005, inf = 1 << 30;
int n, m, s, t, d[maxn], now[maxm];
//d数组上面提到了,now数组为当前弧优化
int tot = 1, to[maxm << 1], head[maxn], nxt[maxm << 1], cap[maxm << 1];
//链式前向星存图(好用)
ll maxflow;//不开ll见祖宗
queue <int> q;
void add(int u, int v, int w){
to[++tot] = v, cap[tot] = w, nxt[tot] = head[u], head[u] = tot;
}
bool BFS(){//BFS寻找增广路
memset(d, 0, sizeof(d));
while (q.size()) q.pop();
q.push(s); d[s] = 1; now[s] = head[s];
while (q.size()){
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (!d[y] && cap[i]){
q.push(y);
d[y] = d[x] + 1;
now[y] = head[y];//初始化当前弧
if (y == t) return true;
}
}
}
return false;
}
int dinic(int x, int flow){
if (x == t || flow == 0) return flow;//到汇点或者流量无了
int rest = flow, k;//rest为当前的可行流
for (int i = now[x]; i && rest; i = nxt[i]){
//这里千万不要用"&",这里如果取址的话,会慢很多,这就是为什么有的人加了当前弧就慢的要死(比如我)
now[x] = i;
int y = to[i];
if (d[y] == d[x] + 1 && cap[i]){//分层图阿巴阿巴
k = dinic(y, min(rest, cap[i]));//显然
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;//增广后可行流减少
}
}
return flow - rest;//返回已经增广的流量
}
int main(){
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i = 1; i <= m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, 0);
//这边我们把每条边建一条反边,其实就是反悔机制(还是很好理解的吧)
}
ll flow = 0;
while (BFS())
while (flow = dinic(s, inf)) maxflow += flow;
printf("%lld", maxflow);
return 0;
}
这里我们主要有两个优化,
一个是多路增广,
一个是当前弧.
\(ISAP\)
如果你嫌 \(dinic\) 不够快的话(其实大部分情况下都够的),
那就学一下 \(ISAP\) 吧( \(HLPP\) 的话...毕竟法律规定,不卡 \(dinic/ISAP\)).
基于我们上面的介绍,
我们可以发现,
\(dinic\) 需要多次 \(BFS\) 来构建多次分层图,
虽然每次都可以增广多路,
但是还是要多次构造(废话).
那么我们可不可以只跑一次分层图呢?
当然可以,
这就是我们的 \(ISAP\) 算法.
这里我们定义一个 \(d\) 数组,
\(d_i\) 代表 \(i\) 节点到 \(t\) 的最短距离,
注意,
这里与 \(dinic\) 中的 \(d\) 相反,
我们很容易就可以发现,
当 \(d_s \geq n\) 时,
就莫得增广路了,
我们就可以终止算法了.
我们再定义一个 \(gap\) 数组(这就是传说中的 \(gap\) 优化),
\(gap_i\) 代表距离 \(t\) 为 \(i\) 的节点数.
这里我们很容易可以看出,
当任意不为 \(0\) 的 \(gap\) 变为 \(0\) 时,
这个图就出现了断层,
然后直接终止算法就可了.
这里的终止指的是至少把图 \(DFS\) 一遍,
把所有的增广路跑完(防止有增广路没增广).
代码大部分与 \(dinic\) 相似.
代码如下⬇️
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5, inf = 1 << 30;
int n, m, now[maxn], d[maxn], gap[maxn], s, t;
int tot = 1, to[maxn], nxt[maxn], head[maxn], cap[maxn];
ll maxflow;
queue <int> q;
int read(){
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
void add(int x, int y, int z){
to[++tot] = y, cap[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void BFS(){
q.push(t); now[t] = head[t]; d[t] = 1; gap[1]++;
while (q.size()){
int x = q.front(); q.pop();
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (!d[y]){
q.push(y);
d[y] = d[x] + 1;
gap[d[y]]++;
}
}
}
}
inline int ISAP(int x, int flow){
if (x == t || flow == 0){
maxflow += flow;
return flow;
}
int rest = flow, k;
for (int i = now[x]; i;i = nxt[i]){
now[x] = i;
int y = to[i];
if (d[y] == d[x] - 1 && cap[i]){
k = ISAP(y, min(rest, cap[i]));
if (k){
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
if (rest == 0) return flow;
}
}
gap[d[x]]--;
if (!gap[d[x]]) d[s] = n + 1;//出现断层,结束程序,但是至少会遍历一遍.
d[x]++;
gap[d[x]]++;
return flow - rest;
}
int main(){
n = read(); m = read(); s = read(); t = read();
for (int i = 1; i <= m; i++){
int u, v, w;
u = read(); v = read(); w = read();
add(u, v, w); add(v, u, 0);
}
BFS();
while (d[s] <= n){
for (int i = 1; i <= n; i++) now[i] = head[i];
ISAP(s, inf);
}
printf("%lld", maxflow);
return 0;
}
最大流完结撒花~
费用流
费用流问题,
也就是最大流最小费用流(最大费用流也一样),
这里其实很简单,
每条边多了一个单位流量,
我们就只需要把 \(dinic/EK\) 中的 \(BFS\) 换成 \(SPFA\) 就可以了.
如果你嫌 \(SPFA\) 慢的话,
可以学一下消圏算法,
这样就可以用 \(dijkstra\) 了.
代码如下⬇️
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, inf = 1 << 30;
int n, m, s, t, d[maxn], flow[maxn], pre[maxn], last[maxn];
//d为当前点所连边的费用,flow为当前点所连边的流量,pre为当前点的前驱,last为当前点所连边的编号
int tot = 1, to[maxn], cap[maxn], cost[maxn], head[maxn], nxt[maxn];
ll maxflow, mincost;
bool vis[maxn];
queue <int> q;
int read(){
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9'){
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void add(int u, int v, int w, int c){
to[++tot] = v, cap[tot] = w, cost[tot] = c, nxt[tot] = head[u], head[u] = tot;
}
bool SPFA(){
memset(d, 0x3f, sizeof(d));
memset(flow, 0x3f, sizeof(flow));
memset(vis, 0, sizeof(vis));
q.push(s);
d[s] = 0; pre[t] = -1;
while (q.size()){
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]){
int y = to[i], z = cost[i];
if (d[y] > d[x] + z && cap[i]){
d[y] = d[x] + z;
pre[y] = x;
last[y] = i;
flow[y] = min(flow[x], cap[i]);
if (vis[y] == 0){
q.push(y);
vis[y] = 1;
}
}
}
}
return pre[t] != -1;
}
void MCMF(){//这里用的是基于EK的MCMF
while (SPFA()){
int now = t;
maxflow += flow[t];
mincost += 1ll * flow[t] * d[t];
while (now != s){
cap[last[now]] -= flow[t];
cap[last[now] ^ 1] += flow[t];
now = pre[now];
}
}
}
int main(){
n = read(), m = read(), s = read(), t = read();
for (int i = 1; i <= m; i++){
int u = read(), v = read(), w = read(), c = read();
add(u, v, w, c);
add(v, u, 0, -c);
}
MCMF();
printf("%lld %lld", maxflow, mincost);
return 0;
}
\(dinic\) 版的
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
typedef long long ll;
const int N = 5e4 + 5, M = 1e5 + 5, inf = 1 << 30;
int n, m, s, t, d[N], now[N];
int tot = 1, to[M], cap[M], cost[M], nxt[M], head[N];
bool vis[N];
ll maxflow, mincost;
int read(){
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)){
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void add(int u, int v, int w, int c){
to[++tot] = v, cap[tot] = w, cost[tot] = c, nxt[tot] = head[u], head[u] = tot;
}
bool SPFA(){
memset(d, 0x3f, sizeof(int) * (n + 1));
memset(vis, 0, sizeof(int) * (n + 1));
std::queue <int> q;
q.push(s); d[s] = 0; now[s] = head[s]; d[t] = inf;
while (q.size()){
int x = q.front(); q.pop();
vis[x] = 0;
for (int i = head[x]; i; i = nxt[i]){
int y = to[i], z = cost[i];
if (d[y] > d[x] + z && cap[i]){
d[y] = d[x] + z;
now[y] = head[y];
if (!vis[y]){
vis[y] = 1;
q.push(y);
}
}
}
}
return d[t] != inf;
}
int dinic(int x, int flow){
if (x == t || flow == 0){
maxflow += flow;
return flow;
}
vis[x] = 1;
int rest = flow, k, i = now[x];
for (; i && rest; i = nxt[i]){
int y = to[i], z = cost[i];
if (!vis[y] && cap[i] && d[y] == d[x] + z){
k = dinic(y, std::min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
mincost += k * cost[i];
}
}
now[x] = i;
vis[x] = 0;
return flow - rest;
}
int main(){
n = read(), m = read(); s = read(), t = read();
for (int i = 1; i <= m; i++){
int u = read(), v = read(), w = read(), c = read();
add(u, v, w, c); add(v, u, 0, -c);
}
while (SPFA())
while (dinic(s, inf));
printf("%lld %lld", maxflow, mincost);
return 0;
}
恭喜你已经学会网络流啦!
不过还是得多刷题,
网络流模型太多了.