所谓上下界网络流，就是在网络图中给每条边指定一个流量下界和上界。这类网络流问题有很多模型，需要根据不同性质进行转化。

网络流系列文章

  1. 最大流
  2. 最小割
  3. 费用流
  4. 上下界网络流

概述

本文中，我们用 $(u, v, l, r)$ 来表示边 $(u, v)$ 的容量的下界为 $l$、上界为 $r$；用 $s', t'$ 表示虚源点和虚汇点；用 $s, t$ 表示源点和汇点。

我们将上下界网络流问题分成若干类，下文将具体展开讲述。

无源汇可行流

思路

首先我们需要增加虚源点和虚汇点，然后考虑如何建图。对于边 $(u, v, l, r)$，流量 $l$ 是必须流过的，流量 $r - l$ 是自由流量。换言之，如果我们强制从 $u$ 流出 $l$ 的流量，强制向 $v$ 流入 $l$ 的流量，那么就可以转化为容量为 $r - l$ 的一般网络流问题了。

这个问题看似比较难处理，那么我们先考虑一个判定性问题：这种网络图是否有可行流？通过上述分析可以将这个问题转化为：是否可以从 $u$ 流出 $l$ 的流量，向 $v$ 流入 $l$ 的流量？

现在这个问题已经比较容易了，我们将边 $(u, v, l, r)$ 拆成如下 $3$ 条边：

  1. 边 $(s', v)​$，容量为 $l​$，也就是强制向 $v​$ 流入 $l​$ 的流量。
  2. 边 $(u, t')$，容量为 $l$，也就是强制从 $u$ 流出 $l$ 的流量。
  3. 边 $(u, v)$，容量为 $r - l$，也就是自由流量。

下文将前 $2$ 条边称为附加边。

接下来在这种图上跑最大流。判断是否可行的方法为：附加边是否满流；换言之就是最大流是否为所有边的下界容量之和。

如果有解，我们只需要将每条边的流量加上下界容量就是一组可行流了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 4e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, low[M], deg[N], dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M];

void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs(int s, int t) {
    memset(dis, -1, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] < 0) {
                q.push(v), dis[v] = dis[u] + 1;
            }
        }
    }
    return dis[t] >= 0;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && dis[v] == dis[u] + 1) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) return ans;
        }
    }
    dis[u] = -1;
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, l, r;
        scanf("%d%d%d%d", &u, &v, &l, &r);
        deg[u] -= l, deg[v] += l, low[i] = l;
        addEdge(u, v, r - l);
    }
    int ss = 0, tt = n + 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i];
        if (deg[i] < 0) addEdge(i, tt, -deg[i]);
    }
    if (dinic(ss, tt) != sum) {
        puts("No");
    } else {
        puts("Yes");
        for (int i = 1; i <= m; i++) {
            printf("%d\n", cap[(i << 1) | 1] + low[i]);
        }
    }
    return 0;
}

有源汇可行流

思路

我们发现，此时源点和汇点不满足流量平衡，那么我们连一条边 $(t, s, 0, \infty)$ 使得源点流向汇点的流量重新流回去。经过转化，有源汇可行流也转化为了无源汇可行流问题。我们只需要和无源汇问题一样拆边建模即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 4e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, s, t, low[M], deg[N], dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M];

void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs(int s, int t) {
    memset(dis, -1, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] < 0) {
                q.push(v), dis[v] = dis[u] + 1;
            }
        }
    }
    return dis[t] >= 0;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && dis[v] == dis[u] + 1) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) return ans;
        }
    }
    dis[u] = -1;
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, l, r;
        scanf("%d%d%d%d", &u, &v, &l, &r);
        deg[u] -= l, deg[v] += l, low[i] = l;
        addEdge(u, v, r - l);
    }
    addEdge(t, s, INF);
    int ss = 0, tt = n + 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i];
        if (deg[i] < 0) addEdge(i, tt, -deg[i]);
    }
    if (dinic(ss, tt) != sum) {
        puts("No");
    } else {
        puts("Yes");
        for (int i = 1; i <= m; i++) {
            printf("%d\n", cap[(i << 1) | 1] + low[i]);
        }
    }
    return 0;
}

有源汇最大流

思路

首先我们按照有源汇可行流的方法进行建模，接下来的讨论均在存在可行流的情况下进行。

在网络图上先得到从 $s'$ 到 $t'$ 的可行流，之后在残量网络上跑一遍从 $s$ 到 $t$ 的最大流，此时得到的最大流就是答案。

这个算法的正确性证明如下：由于我们在原图上跑过最大流，在附加边满流的情况下，我们已经把流量下界这个条件消去了。这样一来，在新图中的 $s$ 到 $t$ 的任何一种可行流都是原图的可行流，这样跑出来的最大流就是原图的最大流。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 4e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, s, t, deg[N], dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M];

void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs(int s, int t) {
    memset(dis, -1, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] < 0) {
                q.push(v), dis[v] = dis[u] + 1;
            }
        }
    }
    return dis[t] >= 0;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && dis[v] == dis[u] + 1) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) return ans;
        }
    }
    dis[u] = -1;
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, l, r;
        scanf("%d%d%d%d", &u, &v, &l, &r);
        deg[u] -= l, deg[v] += l;
        addEdge(u, v, r - l);
    }
    int ss = 0, tt = n + 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i];
        if (deg[i] < 0) addEdge(i, tt, -deg[i]);
    }
    addEdge(t, s, INF);
    printf("%d\n", dinic(ss, tt) == sum ? dinic(s, t) : -1);
    return 0;
}

有源汇最小流

思路

建图方式和最大流一样，但是不要建立 $(t, s, 0, \infty)$ 这条边。在这种图上我们得到 $s'$ 到 $t'$ 的最大流；之后连上 $(t, s, 0, \infty)$ 这条边得到新图上的最大流；此时的最大流就是原图的最小流。

考虑证明这个过程的正确性。之前讲过，边 $(t, s)$ 上的流量就是原图的流量；现在我们要最小化这个值，就要尽可能多消耗掉可能要经过这条边的流量。第一次跑最大流的时候没有连上这条边，因此 $s$ 到 $t$ 的流量已经尽可能往别的地方流了，就可以最小化这个值了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 4e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, s, t, deg[N], dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M];

void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);
}
bool bfs(int s, int t) {
    memset(dis, -1, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] < 0) {
                q.push(v), dis[v] = dis[u] + 1;
            }
        }
    }
    return dis[t] >= 0;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && dis[v] == dis[u] + 1) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) return ans;
        }
    }
    dis[u] = -1;
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, l, r;
        scanf("%d%d%d%d", &u, &v, &l, &r);
        deg[u] -= l, deg[v] += l;
        addEdge(u, v, r - l);
    }
    int ss = 0, tt = n + 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) addEdge(ss, i, deg[i]), sum += deg[i];
        if (deg[i] < 0) addEdge(i, tt, -deg[i]);
    }
    int ans = dinic(ss, tt);
    addEdge(t, s, INF);
    ans += dinic(ss, tt);
    printf("%d\n", ans == sum ? cap[tot] : -1);
    return 0;
}

有源汇费用流

思路

首先需要注意的是：上下界网络流中的最小费用流没有最大流前提，而是可行流的最小费用！

这个过程和有源汇可行流很相似。对于一条边 $(u, v, l, r, c)$，我们将其拆成 $3$ 条边：

  1. 边 $(s', v)$，容量为 $l$，费用为 $0$。
  2. 边 $(u, t')$，容量为 $l$，费用为 $0$。
  3. 边 $(u, v)$，容量为 $r - l$，费用为 $c$。

按照套路，我们还要连边 $(t, s, 0, \infty, 0)$，当然费用也是 $0$。我们求出 $s'$ 到 $t'$ 的最小费用最大流，最终的费用还要加上每条边的下界乘上其费用。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e5 + 5, M = 4e5 + 5;
const int INF = 0x7f7f7f7f;

int n, m, s, t, low[N], deg[N], dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M];
bool vis[N];

void add(int u, int v, int w, int c) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addEdge(int u, int v, int w, int c) {
    add(u, v, w, c), add(v, u, 0, -c);
}
bool spfa(int s, int t) {
    memset(dis, 0x7f, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0, vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = false;
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] > dis[u] + cost[i]) {
                dis[v] = dis[u] + cost[i];
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
    return dis[t] < INF;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    vis[u] = true;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) break;
        }
    }
    vis[u] = false;
    return ans;
}
std::pair<int, int> dinic(int s, int t) {
    int maxFlow = 0, minCost = 0;
    while (spfa(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) maxFlow += x, minCost += x * dis[t];
    }
    return std::make_pair(maxFlow, minCost);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, l, r, c;
        scanf("%d%d%d%d%d", &u, &v, &l, &r, &c);
        deg[u] -= l, deg[v] += l, low[i] = l;
        addEdge(u, v, r - l, c);
    }
    int ss = 0, tt = n + 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) addEdge(ss, i, deg[i], 0), sum += deg[i];
        if (deg[i] < 0) addEdge(i, tt, -deg[i], 0);
    }
    addEdge(t, s, INF, 0);
    std::pair<int, int> ans = dinic(ss, tt);
    if (ans.first != sum) {
        puts("-1");
    } else {
        for (int i = 1; i <= m; i++) {
            ans.second += low[i] * cost[i << 1];
        }
        printf("%d %d\n", ans.first, ans.second);
    }
    return 0;
}

习题

网络流 24 题

最后修改：2019 年 06 月 01 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏