[学习笔记] 有上下界网络流 - 理论与实现

有上下界网络流

1 基本型无源无汇有上下界可行流

对于边\(e\)，设其流量区间为 \([l,r]\) ，则将流量分解为两部分，一部分 \(l\) 成为必须流，另一部分 \(r−l\) 成为可选流.

那么我们建超级源点 \(S\) 和超级源点 \(T\) ，连边 \(S→v\) , \(u→T\) 容量均为 \(l\)，连边 \(u→v\) 容量为 \(r−l\)，从 \(S→T\)跑最大流后，网络上每条边的流量加上它的下界就是答案。

考虑到这样重边较多，我们可以对图稍作简化。考虑到每个点最终只有超级流入和超级流出中的一个是有效的，我们先不将点和超级源汇连边，先记录它的 \(extra\) 值，建图完成后根据每个点的 \(extra\) 值决定它与 \(S\) 还是 \(T\) 连边，容量为多少，这样可以大幅度简化。

2 扩展型

本节中的所有问题最终都被规约成基本型进行求解。

2.1 有源有汇有上下界可行流

为防止混淆，将这里的实际源汇记为 \(s,t\)，而先前的超级点记为 \(S,T\) 。我们暴力让 \(s,t\) 也满足流量平衡，即连一条 \(t→s\) 的容量为 \(\infty\) 的边，这样就转化为基本型。

2.2 有源有汇有上下界最大流

求出有源有汇有上下界可行流后，我们直接在残量网络上从 \(s\) 到 \(t\) 增广，得到最大流。由于这里进行了两次增广，我们需要考虑清楚答案到底是什么。具体而言，第一次求出的仅仅是全部满足界的流量，第二次求出的是在此基础上畅通的自由流的流量。我们用第一次的答案来判定可行性，如果可行那么答案就是第二次增广过程中增加的流量。

2.3 有源有汇有上下界最小流

本质上和最大流相同，只是附加增广改为从 \(t\) 到 \(s\) 增广，但注意此时需要删除 \(t\) 到 \(s\) 的那条附加边。这里的答案等于删去的那条附加边上的流量减去第二次增广的最大流。

3 参考程序

3.1 无源无汇有上下界可行流

#include <bits/stdc++.h>
using namespace std;
const int MAX_NODE = 1000005;
namespace Network {
int tInfinity = 1e+9;
struct edge {
    int p, o;
    int c, id;
};
int s, t;
int ans, tans;
int dis[MAX_NODE];
vector<edge> g[MAX_NODE];
void make_edge(int p, int q, int c, int id) {
    int sz1 = g[p].size(), sz2 = g[q].size();
    edge tmp;
    tmp.p = q;
    tmp.c = c;
    tmp.o = sz2;
    tmp.id = id;
    g[p].push_back(tmp);
    tmp.p = p;
    tmp.c = 0;
    tmp.o = sz1;
    tmp.id = 0;
    g[q].push_back(tmp);
}
void reset_graph(int maxnode) {
    for (int i = 0; i <= maxnode; i++) g[i].clear();
}
int dinic_bfs() {
    queue<int> q;
    q.push(s);
    memset(dis, 0xff, sizeof dis);
    dis[s] = 1;
    while (q.size()) {
        int p = q.front();
        q.pop();
        for (int i = 0; i < g[p].size(); i++)
            if (g[p][i].c > 0 && dis[g[p][i].p] < 0)
                q.push(g[p][i].p), dis[g[p][i].p] = dis[p] + 1;
    }
    return dis[t] > 0;
}
int dinic_dfs(int p, int lim) {
    int flow = 0;
    if (p == t)
        return lim;
    for (int i = 0; i < g[p].size(); i++) {
        if (g[p][i].c > 0 && dis[g[p][i].p] == dis[p] + 1) {
            int tmp = dinic_dfs(g[p][i].p, min(lim, g[p][i].c));
            if (tmp > 0) {
                g[p][i].c -= tmp;
                g[g[p][i].p][g[p][i].o].c += tmp;
                flow += tmp;
                lim -= tmp;
            }
        }
    }
    return flow;
}
int solve(int src, int tar) {
    s = src;
    t = tar;
    ans = 0;
    tans = 0;
    while (dinic_bfs()) {
        while (tans = dinic_dfs(s, tInfinity)) {
            ans += tans;
        }
    }
    return ans;
}
};  // namespace Network

int n, m, s, t, low, upp, E[MAX_NODE][5];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    int sum = 0;
    for (int i = 1; i <= m; i++) {
        cin >> s >> t >> low >> upp;
        E[i][0] = s;
        E[i][1] = t;
        E[i][2] = low;
        E[i][3] = upp;
        Network::make_edge(n + 1, t, low, 0);
        Network::make_edge(s, n + 2, low, 0);
        Network::make_edge(s, t, upp - low, i);
        sum += low;
    }
    if (sum == Network::solve(n + 1, n + 2)) {
        cout << "YES" << endl;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < Network::g[i].size(); j++) E[Network::g[i][j].id][4] = Network::g[i][j].c;
        }
        for (int i = 1; i <= m; i++) {
            cout << E[i][3] - E[i][4] << endl;
        }
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

3.2 有源有汇有上下界最大流

#include <bits/stdc++.h>
using namespace std;
const int MAX_NODE = 1000005;
namespace Network {
int tInfinity = 1e+9;
struct edge {
    int p, o;
    int c, id;
};
int s, t;
int ans, tans;
int dis[MAX_NODE];
vector<edge> g[MAX_NODE];
void make_edge(int p, int q, int c, int id) {
    int sz1 = g[p].size(), sz2 = g[q].size();
    edge tmp;
    tmp.p = q;
    tmp.c = c;
    tmp.o = sz2;
    tmp.id = id;
    g[p].push_back(tmp);
    tmp.p = p;
    tmp.c = 0;
    tmp.o = sz1;
    tmp.id = 0;
    g[q].push_back(tmp);
}
void reset_graph(int maxnode) {
    for (int i = 0; i <= maxnode; i++) g[i].clear();
}
int dinic_bfs() {
    queue<int> q;
    q.push(s);
    memset(dis, 0xff, sizeof dis);
    dis[s] = 1;
    while (q.size()) {
        int p = q.front();
        q.pop();
        for (int i = 0; i < g[p].size(); i++)
            if (g[p][i].c > 0 && dis[g[p][i].p] < 0)
                q.push(g[p][i].p), dis[g[p][i].p] = dis[p] + 1;
    }
    return dis[t] > 0;
}
int dinic_dfs(int p, int lim) {
    int flow = 0;
    if (p == t)
        return lim;
    for (int i = 0; i < g[p].size(); i++) {
        if (g[p][i].c > 0 && dis[g[p][i].p] == dis[p] + 1) {
            int tmp = dinic_dfs(g[p][i].p, min(lim, g[p][i].c));
            if (tmp > 0) {
                g[p][i].c -= tmp;
                g[g[p][i].p][g[p][i].o].c += tmp;
                flow += tmp;
                lim -= tmp;
            }
        }
    }
    return flow;
}
int solve(int src, int tar) {
    s = src;
    t = tar;
    ans = 0;
    tans = 0;
    while (dinic_bfs()) {
        while (tans = dinic_dfs(s, tInfinity)) {
            ans += tans;
        }
    }
    return ans;
}
};  // namespace Network

int n, m, s, t, ps, pt, low, upp, E[MAX_NODE][5];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> ps >> pt;
    int sum = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        cin >> s >> t >> low >> upp;
        E[i][0] = s;
        E[i][1] = t;
        E[i][2] = low;
        E[i][3] = upp;
        Network::make_edge(n + 1, t, low, 0);
        Network::make_edge(s, n + 2, low, 0);
        Network::make_edge(s, t, upp - low, i);
        sum += low;
    }
    Network::make_edge(pt, ps, 1e+9, 0);
    if (sum == Network::solve(n + 1, n + 2)) {
        ans = Network::solve(ps, pt);
        cout << ans << endl;
    } else {
        cout << "please go home to sleep" << endl;
    }
    return 0;
}

3.3 有源有汇有上下界最小流

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_NODE = 1000005;
namespace Network {
ll tInfinity = 1e+15;
struct edge {
    ll p, o;
    ll c, id;
};
ll s, t;
ll ans, tans;
ll dis[MAX_NODE];
vector<edge> g[MAX_NODE];
void make_edge(ll p, ll q, ll c, ll id) {
    ll sz1 = g[p].size(), sz2 = g[q].size();
    edge tmp;
    tmp.p = q;
    tmp.c = c;
    tmp.o = sz2;
    tmp.id = id;
    g[p].push_back(tmp);
    tmp.p = p;
    tmp.c = 0;
    tmp.o = sz1;
    tmp.id = -id;
    g[q].push_back(tmp);
}
void reset_graph(ll maxnode) {
    for (ll i = 0; i <= maxnode; i++) g[i].clear();
}
ll dinic_bfs() {
    queue<ll> q;
    q.push(s);
    memset(dis, 0xff, sizeof dis);
    dis[s] = 1;
    while (q.size()) {
        ll p = q.front();
        q.pop();
        for (ll i = 0; i < g[p].size(); i++)
            if (g[p][i].c > 0 && dis[g[p][i].p] < 0)
                q.push(g[p][i].p), dis[g[p][i].p] = dis[p] + 1;
    }
    return dis[t] > 0;
}
ll dinic_dfs(ll p, ll lim) {
    ll flow = 0;
    if (p == t)
        return lim;
    for (ll i = 0; i < g[p].size(); i++) {
        if (g[p][i].c > 0 && dis[g[p][i].p] == dis[p] + 1) {
            ll tmp = dinic_dfs(g[p][i].p, min(lim, g[p][i].c));
            if (tmp > 0) {
                g[p][i].c -= tmp;
                g[g[p][i].p][g[p][i].o].c += tmp;
                flow += tmp;
                lim -= tmp;
            }
        }
    }
    return flow;
}
ll solve(ll src, ll tar) {
    s = src;
    t = tar;
    ans = 0;
    tans = 0;
    while (dinic_bfs()) {
        while (tans = dinic_dfs(s, tInfinity)) {
            ans += tans;
        }
    }
    return ans;
}
};  // namespace Network

ll n, m, s, t, ps, pt, low, upp, E[MAX_NODE][5];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> ps >> pt;
    ll sum = 0, ans = 0;
    for (ll i = 1; i <= m; i++) {
        cin >> s >> t >> low >> upp;
        E[i][0] = s;
        E[i][1] = t;
        E[i][2] = low;
        E[i][3] = upp;
        Network::make_edge(n + 1, t, low, i);
        Network::make_edge(s, n + 2, low, i);
        Network::make_edge(s, t, upp - low, i);
        sum += low;
    }
    Network::make_edge(pt, ps, 1e+15, 0);
    if (sum == (Network::solve(n + 1, n + 2))) {
        for (int i = 0; i < Network::g[ps].size(); i++)
            if (Network::g[ps][i].id == 0)
                ans = Network::g[ps][i].c, Network::g[ps][i].c = 0;
        for (int i = 0; i < Network::g[pt].size(); i++)
            if (Network::g[pt][i].id == 0)
                Network::g[pt][i].c = 0;
        ans -= Network::solve(pt, ps);
        cout << ans << endl;
    } else {
        cout << "please go home to sleep" << endl;
    }
    return 0;
}

下界