526互联

网络流学习笔记

发布时间 2023-03-31 22:14:31作者: panhongxuan

前言

我最近在刷网络流的题，结果啥都不会做……

把一些学习中的心得放到这里，很垃圾，请巨佬们不要吐槽。

没时间写，目前先把模板放到这吧

（未完待续）

本文写作时间：2023.3.30 22.16 ~ ?

本文发布在洛谷博客，博客园。

网络流算法

Ford-Fulkerson 算法

Ford-Fulkerson 算法（简称 FF）是最原始的网络流算法，时间复杂度上限 \(O(nm^2)\)。

要注意网络流算法的时间复杂度都是玄学，往往跑不满，所以 FF 实际上耗时比 \(O(nm^2)\) 小很多，但是仍然很慢。

（未完待续）

Edmond-Karp 算法

Edmond-Karp 算法（简称 EK）是 FF 的 bfs 版，时间复杂度上限 \(O(nm^2)\)，但是往往比 FF 跑得更快。

（未完待续）

Dinic 算法

Dinic 算法应该可以算最常用的网络流算法，既好写，时间复杂度上限又比 FF 和 EK 低很多，是 \(O(n^2 m)\)，跑得比较快。

（未完待续）

Code

下面是P3376 【模板】网络最大流的代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1000, maxm = 20000;
const ll N = maxn * 2 + 10, M = maxm + 10;
const ll INF = 0x3f3f3f3f3f3f3fll;
ll n, m, num, s, t, S, ans, H[N], C[N], de[N];
struct edg{
    ll t, nxt, len;
}E[M * 2];
void add_edg(ll x, ll y, ll w) {
    ++num;
    E[num].t = y;
    E[num].nxt = H[x];
    E[num].len = w;
    H[x] = num;
}
void add_edges(ll x, ll y, ll w) {
    add_edg(x, y, w);
    add_edg(y, x, 0);
}
ll dfs(ll x, ll y) {
    if (x == t) {
        return y;
    }
    ll z = y, res = 0;
    for (ll i = C[x]; i > 0 && z > 0; i = E[i].nxt) {
        C[x] = i;
        ll v = E[i].t, w = E[i].len;
        if (w > 0 && de[v] != -1 && de[v] == de[x] + 1) {
            ll k = dfs(v, min(w, z));
            E[i].len -= k;
            E[(i ^ 1)].len += k;
            z -= k;
            res += k;
        }
    }
    return res;
}
bool bfs() {
    for (ll i = 1; i <= S; ++i) {
        de[i] = -1;
        C[i] = H[i];
    }
    de[s] = 1;
    queue<ll> q;
    q.push(s);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        for (ll i = H[x]; i > 0; i = E[i].nxt) {
            ll v = E[i].t, w = E[i].len;
            if (w > 0 && de[v] == -1) {
                de[v] = de[x] + 1;
                q.push(v);
            }
        }
    }
    return (de[t] != -1);
}
int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    num = 1;
    S = n;
    for (ll i = 1; i <= m; ++i) {
        ll u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add_edges(u, v, w);
    }
    ans = 0;
    while (bfs()) {
        ll k = dfs(s, INF);
        ans += k;
    }
    printf("%lld", ans);
    return 0;
}

ISAP 算法

ISAP 算法的时间复杂度上限和 Dinic 一样，都是 \(O(n^2 m)\) 的，但是往往比 Dinic 跑得更快。

（未完待续）

注： 我的模板因为使用每次通过寻找出边中深度的最小值并更新该点的深度的写法，有点问题，被我 hack 了 2 次，下面是两个 hack 样例：

第 1 个：

input:

7 8 1 7
1 2 1
1 3 1
2 4 1
3 4 1
4 7 1
4 5 1
5 7 1
4 6 2147483647

output:

2

wrong output:

1

第 2 个：

input:

8 9 6 7
6 1 2
1 3 2
3 8 2
8 7 2
1 2 2147483647
2 7 1
6 4 1
4 5 1
5 2 1

output:

3

wrong output:

2

注意：因此，最好写直接把深度加 \(1\) 的写法，既正确性高，又常数小！

Code

下面是P3376 【模板】网络最大流的代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 400, maxm = 20000;
const ll N = maxn * 2 + 10, M = maxm + 10;
const ll INF = 0x3f3f3f3f3f3f3fll;
ll n, m, num, s, t, S, ans, H[N], C[N], de[N], gp[N];
bool fl;
struct edg{
    ll t, nxt, len;
}E[M * 2];
void add_edg(ll x, ll y, ll w) {
    ++num;
    E[num].t = y;
    E[num].nxt = H[x];
    E[num].len = w;
    H[x] = num;
}
void add_edges(ll x, ll y, ll w) {
    add_edg(x, y, w);
    add_edg(y, x, 0);
}
ll dfs(ll x, ll y) {
    if (x == t) {
        return y;
    }
    ll z = y, res = 0;
    for (ll i = C[x]; i > 0 && z > 0; i = E[i].nxt) {
        C[x] = i;
        ll v = E[i].t, w = E[i].len;
        if (w > 0 && de[v] != -1 && de[v] + 1 == de[x]) {
            ll k = dfs(v, min(w, z));
        
            E[i].len -= k;
            E[(i ^ 1)].len += k;
            z -= k;
            res += k;
            if (z == 0) {
                return res;
            }
        }
    }
    --gp[de[x]];
    if (gp[de[x]] == 0) {
        fl = 0;
    }
    ++de[x];
    ++gp[de[x]];
    return res;
}
void bfs() {
    for (ll i = 1; i <= S; ++i) {
        de[i] = -1;
    }
    de[t] = 1;
    for (ll i = 1; i <= S + 1; ++i) {
        gp[i] = 0;
    }
    queue<ll> q;
    q.push(t);
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        ++gp[de[x]];
        for (ll i = H[x]; i > 0; i = E[i].nxt) {
            ll v = E[i].t;
            if (i % 2 == 1 && de[v] == -1) {
                de[v] = de[x] + 1;
                q.push(v);
            }
        }
    }
}
void ISAP() {
    bfs();
    fl = 1;
    while (de[s] <= S && fl) {
        for (ll i = 1; i <= S; ++i) {
            C[i] = H[i];
        }
        fl = 1;
        ll k = dfs(s, INF);
        ans += k;
    }
}
int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    num = 1;
    S = n;
    for (ll i = 1; i <= m; ++i) {
        ll u, v, w;
        scanf("%lld%lld%lld", &u, &v, &w);
        add_edges(u, v, w);
    }
    ISAP();
    printf("%lld", ans);
    return 0;
}

HLPP 算法

最快的网络流算法，时间复杂度 \(O(n^2 \sqrt{m})\)，我还不会……

（未完待续）

最小（大）费用最大流

最小（大）费用最大流是网络最大流的拓展，每一条边除了容量之外，还增加了一个费用，整张网络的总费用为每一条边的流量乘费用的和。在保证流量最大的前提下，要求出最小（大）的费用。

最大费用最大流跑最长路即可。

（未完待续）

Code

下面是P3381 【模板】最小费用最大流的代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 20000, maxm = 200000;
const ll N = maxn * 2 + 10, M = maxm + 10;
const ll INF = 0x3f3f3f3f3f3f3fll;
ll n, m, num, s, t, S, ans1, ans2, H[N], C[N], dis[N];
bool b[N], vis[N];
struct edg{
    ll t, nxt, len, k;
}E[M * 2];
void add_edg(ll x, ll y, ll w, ll k) {
    ++num;
    E[num].t = y;
    E[num].nxt = H[x];
    E[num].len = w;
    E[num].k = k;
    H[x] = num;
}
void add_edges(ll x, ll y, ll w, ll k) {
    add_edg(x, y, w, k);
    add_edg(y, x, 0, -k);
}
ll dfs(ll x, ll y) {
    if (x == t) {
        return y;
    }
    vis[x] = 1;
    ll z = y, res = 0;
    for (ll i = C[x]; i > 0 && z > 0; i = E[i].nxt) {
        C[x] = i;
        ll v = E[i].t, w = E[i].len, k = E[i].k;
        if (w > 0 && (!vis[v]) && dis[v] == dis[x] + k) {
            ll k = dfs(v, min(w, z));
            E[i].len -= k;
            E[(i ^ 1)].len += k;
            z -= k;
            res += k;
        }
    }
    return res;
}
bool bfs() {
    for (ll i = 1; i <= S; ++i) {
        C[i] = H[i];
        dis[i] = INF;
        b[i] = 0;
        vis[i] = 0;
    }
    dis[s] = 0;
    bool z = 0;
    queue<ll> q;
    q.push(s);
    b[s] = 1;
    while (!q.empty()) {
        ll x = q.front();
        q.pop();
        if (x == t) {
            z = 1;
        }
        b[x] = 1;
        for (ll i = H[x]; i > 0; i = E[i].nxt) {
            ll v = E[i].t, w = E[i].len, k = E[i].k;
            if (w > 0 && dis[x] + k < dis[v]) {
                dis[v] = dis[x] + k;
                if (!b[v]) {
                    b[v] = 1;
                    q.push(v);
                }
            }
        }
        b[x] = 0;
    }
    return z;
}
int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
    num = 1;
    S = n;
    for (ll i = 1; i <= m; ++i) {
        ll u, v, w, k;
        scanf("%lld%lld%lld%lld", &u, &v, &w, &k);
        add_edges(u, v, w, k);
    }
    ans1 = 0;
    ans2 = 0;
    while (bfs()) {
        ll k = dfs(s, INF);
        ans1 += k;
        ans2 += (k * dis[t]);
    }
    printf("%lld %lld", ans1, ans2);
    return 0;
}

后记

本文更新记录

1.0 版：2023.3.30

最初版本。

1.1版：2023.3.31

发现 ISAP 的模板有 2 个错误，进行了改正，并放上了 2 个 hack 样例。