网络流 学习笔记

网络流

网络流 学习笔记

一些概念

​ 举个栗子：现有 $m$ 根水管连接 $n$ 个点，每根水管每秒通水量的限制为 $c_i$ ，那么求从点 $s$ 输水到 $t$ 一秒最多能输多少水，假设水的速度是无限快的。这样子的问题就是最简单的最大流问题。

​ 我们设 $x, y$ 两个点之间水管的容量为 $c(x,y)$ ，$f(x,y)$ 为 $x$ 实际流向 $y$ 的水，那么 $c(x,y)-f(x,y)$ 称为这条水管的剩余容量 。在任何时刻中，网络中剩余容量大于 $0$ 的边构成的图叫做残量网络。

$f(x,y)$ 会满足下面的限制

• $0 \leq f(x,y) \leq c(x,y)$
• $\forall \; x ≠ s,x ≠ t$ ，有 $\sum_{(u,x) \in E} f(u,x)=\sum_{(x,v) \in E} f(x,v)$ ，也就是流入一个点的水量与其输出量相当

最大流

​ 上面例子里的 $s$ 其实叫做源点，$t$ 叫做汇点。最大流问题就跟上面那个问题一样，求源点到汇点的最大流量。求解最大流问题有很多种算法，笔者比较菜，只会 EK 和 Dinic。

Edmonds-Karp 增广路算法

​ EK 算法，全称 Edmonds-Karp 增广路算法。其主要思路是使用 BFS 找到一条从 $s$ 到 $t$ 的路径，其路径上所有边的剩余容量都大于 $0$ 。我们将这样的一条路径称之为增广路。很明显，这样子可能得不到最优解，所以要建反向边，相当于是可以撤销这条边的流量。

时间复杂度为 $\mathcal{O(nm^2)}$ 。

以下模板用来 AC Luogu 【模板】网络最大流

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
const int INF = 0x3f3f3f3f;
const int MAXN = 1e4;
const int MAXM = 1e5;
int n, m, s, t, edge = -1;
int firstEdge[MAXN | 1], minFlow[MAXN | 1], F[MAXN | 1];
struct Edge {
    int to, w, nxt;
    Edge(){}
    Edge(int x, int y, int z) {
        to = y;
        w = z;
        nxt = firstEdge[x];
    }
} e[MAXM << 1 | 1];
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int x, int y, int z) {
    e[++edge] = Edge(x, y, z);
    firstEdge[x] = edge;
}
bool Augment() {
    bool vis[MAXN | 1];
    std::queue <int> q;
    memset(vis, 0, sizeof(vis));
    q.push(s);
    vis[s] = 1;
    minFlow[s] = INF;
    do {
        int from = q.front();
        q.pop();
        for(int k = firstEdge[from]; k != -1; k = e[k].nxt) {
            int to = e[k].to, w = e[k].w;
            if(w > 0) {
                if(vis[to] == true) continue;
                minFlow[to] = std::min(minFlow[from], w);
                F[to] = k;
                q.push(to);
                vis[to] = 1;
                if(to == t) return true;
            }
        }
    } while(!q.empty());
    return false;
}
int EK() {
    int res = 0;
    while(Augment() == true) {
        res += minFlow[t];
        int tmp = t;
        while(tmp != s) {
            int k = F[tmp];
            e[k].w -= minFlow[t];
            e[k ^ 1].w += minFlow[t];
            tmp = e[k ^ 1].to;
        }
    }
    return res;
}
int main() {
    n = read();
    m = read();
    s = read();
    t = read();
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        addEdge(u, v, w);
        addEdge(v, u, 0);
    }
    printf("%d\n", EK());
    return 0;
}

Dinic 算法

​ Dinic 算法主要思路也是寻找增广路。每次寻找增广路的时候，求出当前残量网络的 BFS 序，然后每次在残量网络上 DFS 找增广路从 $x$ 点出发只能访问到 BFS 序为 $x$ 的 BFS 序 $+1$ 的点。这样子的时间复杂度是 $\mathcal{O(n^2m)}$ ，比较优秀。

以下模板用来 AC Luogu 【模板】网络最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int INF = 0x3f3f3f3f;
const int MAXN = 1e4;
const int MAXM = 1e5;
int n, m, sp, ep, edge = -1;
int firstEdge[MAXN | 1], curE[MAXN | 1], depth[MAXN | 1];
struct Edge {
    int to, w, nxt;
    Edge(){}
    Edge(int x, int y, int z) {
        to = y;
        w = z;
        nxt = firstEdge[x];
    }
} e[MAXM << 1 | 1];
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int x, int y, int z) {
    e[++edge] = Edge(x, y, z);
    firstEdge[x] = edge;
}
bool getDepth() {
    std::queue <int> q;
    memset(depth, 0, sizeof(depth));
    depth[sp] = 1;
    q.push(sp);
    do {
        int from = q.front();
        q.pop();
        for(int k = firstEdge[from]; ~k; k = e[k].nxt) {
            int to = e[k].to, w = e[k].w;
            if(!depth[to] && w > 0) {
                depth[to] = depth[from] + 1;
                q.push(to);
            }
        }
    } while(!q.empty());
    return depth[ep] > 0;
}
int Augment(int x, int flow) {
    if(x == ep) return flow;
    for(int &k = curE[x]; ~k; k = e[k].nxt) {
        int to = e[k].to, w = e[k].w;
        if(depth[to] == depth[x] + 1 && w > 0) {
            int tmp = Augment(to, std::min(flow, w));
            if(tmp > 0) {
                e[k].w -= tmp;
                e[k ^ 1].w += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int Dinic() {
    int res = 0, tmp = 0;
    while(getDepth()) {
        for(int i = 1; i <= n; ++i) curE[i] = firstEdge[i];
        while((tmp = Augment(sp, INF)) > 0) res += tmp;
    }
    return res;
}
int main() {
    n = read();
    m = read();
    sp = read();
    ep = read();
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= m; ++i) {
        int a = read(), b = read(), c = read();
        addEdge(a, b, c);
        addEdge(b, a, 0);
    }
    printf("%d\n", Dinic());
    return 0;
}

最小割

​ 给定一个网络 $G=(V,E)$ ，若某个 $E$ 的子边集被删去，使得源点与汇点不再连通，则该边集称为网络的一个割。容量之和最小的割称为网络的最小割。

最大流最小割定理

任何一个网络里的最大流与最小割的容量相等。

下面来理性感性理解一下：

​ 为了使得源点与汇点不连通，每条源点通往汇点的路径上至少要删去一条边，也就是进入割集。那么贪心的想一想，肯定要删去容量最小的那条边。因为每条路径的流量取决于路径上容量最小的那条边，所以最小割=最大流。

USACO4.4 Pollutant Control

费用流

​ 在之前问题的基础上给每条边除容量外还加上了一个花费，其总花费为总流量乘以总花费。其中总花费最小的最大流称为最小费用最大流，而花费最大的称为最大费用最大流。二者合称费用流模型。费用流的前提是最大流。

我只会 EK 魔改的 SPFA

这个算法的思想就是在 EK 的基础下，找增广路的时候用 SPFA 找一条总费用最小的增广路，剩下的部分与 EK 差不多。

复杂度为 $\mathcal O(fnm)$ ，其中 $f$ 为最大流量。

以下代码用来 AC Luogu 【模板】最小费用最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int INF = 0x3f3f3f3f;
const int MAXN = 5e4;
const int MAXM = 5e5;
int n, m, sp, ep, edge = -1, maxFlow, minCost;
int firstEdge[MAXN | 1], minFlow[MAXN | 1], dist[MAXN | 1], lst[MAXN | 1];
struct Edge {
    int to, f, w, nxt;
    Edge(){}
    Edge(int a, int b, int c, int d) {
        to = b;
        f = c;
        w = d;
        nxt = firstEdge[a];
    }
} e[MAXM << 1 | 1];
inline int read() {
    register int x = 0, v = 1;
    register char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') v = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * v;
}
inline void addEdge(int a, int b, int c, int d) {
    e[++edge] = Edge(a, b, c, d);
    firstEdge[a] = edge;
}
bool Augment() {
    std::queue <int> q;
    bool vis[MAXN | 1];
    while(!q.empty()) q.pop();
    memset(vis, false, sizeof(vis));
    memset(dist, INF, sizeof(dist));
    dist[sp] = 0;
    minFlow[sp] = INF;
    q.push(sp);
    do {
        int from = q.front();
        q.pop();
        vis[from] = false;
        for(int k = firstEdge[from]; ~k; k = e[k].nxt) {
            int to = e[k].to, w = e[k].w, f = e[k].f;
            if(f > 0 && dist[to] > dist[from] + w) {
                dist[to] = dist[from] + w;
                minFlow[to] = std::min(minFlow[from], f);
                lst[to] = k;
                if(!vis[to]) {
                    q.push(to);
                    vis[to] = true;
                }
            }
        }
    } while(!q.empty());
    return dist[ep] != INF;
}
void EK(int flow) {
    while(flow > 0 && Augment()) {
        maxFlow += minFlow[ep];
        minCost += minFlow[ep] * dist[ep];
        flow -= minFlow[ep];
        int tmp = ep;
        while(tmp != sp) {
            e[lst[tmp]].f -= minFlow[ep];
            e[lst[tmp] ^ 1].f += minFlow[ep];
            tmp = e[lst[tmp] ^ 1].to;
        }
    }
}
int main() {
    n = read();
    m = read();
    sp = read();
    ep = read();
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= m; ++i) {
        int a = read(), b = read(), c = read(), d = read();
        addEdge(a, b, c, d);
        addEdge(b, a, 0, -d);
    }
    EK(INF);
    printf("%d %d\n", maxFlow, minCost); 
    return 0;
}

POJ 3422