题解：P14580 【模板】有源汇上下界最小流

· · 题解

1. 无源汇可行流

虽然这是另一道题的东西，但是这是解决这道题的基础，所以我做一些讲解。

先把样例 1 （我自己做了一点改动）拿过来吧。

我们如何判断这个图中，是否存在可行流？其实这个并不困难，我们来一步步分析。

由于这个图中，每一条边的流量有下界，也就是边至少流这么多的流量，所以我们考虑把这些流量先流过去。这一条边剩下的流量就是这一条边的上界减去下界，即 r_i - l_i。

现在这个图就变成这样了（其中蓝色表示已经流过的流量，红色表示还可以流的流量）：

容易发现，现在这不是一个可行流，因为有一些点的流入和流出不是平衡的。流入和流出的平衡性如下图所示（绿色表示流入大于流出，黄色表示流出大于流入，暗红色表示这个节点的流入减流出）：

如果能够形成可行流，那么所有节点的流入应该等于流出，也就是不存在供需不平衡的情况。也就是，我们需要用剩下的流量去“补齐”这些不平衡的点。

那该怎么“补齐”呢？这个时候就需要请出我们的最大流了。建立超级源点和超级汇点，超级源点向每一个绿色的点连边，每一个黄色的点向超级汇点连边，边权为这个点流量不平衡的绝对值。于是这个图就变成了这样：

然后跑出 S\to T 的最大流，如果与 T 相连的所有边都满流，那么有可行流，否则没有。

为什么？因为最大流表示着从源点到汇点最多可以“补齐”的流量，也就是从绿色的点最多能过补到黄色的点的流量，如果与 T 相连的所有边都满流，就标志着每一个供需不平衡的点都可以被补齐。比如上面的图，最大流跑出来是这样的：

令人悲伤的是，由于 3\to T 这一条边没有满流，所以这个图不能形成一个可行流。

哎，等等，不对啊，这不是样例 1 吗，应该有解啊？别急，这是无源汇的情况，所以不能够形成可行流，如果换成有源汇的情况，是可以形成的。

2. 无源汇转有源汇

这一步其实非常简单，我们只需要在原本的源点和汇点之间建一条下界为 0，上界为 \infin 的边就可以了。为什么呢？因为在网络流中，我们可以向源点灌无限多的水，汇点是一个无底洞，可以接受无限多的水。加了这一条边权为 \infin 的边以后，我们向源点就可以最大有 \infin 的流量，汇点也可以最大流出 \infin 的流量，这就契合了源汇的定义。

比如样例，现在就是这样的：

我们还是跑出 S\to T 的最大流，那就是这样的了（注意到由于有那一条新添加的边，所以我们可以通过走 S\to 4\to 5\to 1\to T 来得到满流了，其中紫色表示新增的流量）

现在，3\to T 这一条边满流了，于是这个图就有可行流了。我们得到的可行流的流量就是最大流上这一条边的流量加上原本的流量下界，也就是可行流长这样：

但是，这个可行流并不是最小流，因为还有很多的边还可以退回流量。于是，我们还需要使得流量最小化。

3. 可行流转最小流

在之前的可行流中，我们跑出来一些可行的流量，但是这并不意味着流量最小。有一些边还有一些多余的流量，所以这并不是最大流。

怎么变成最小流呢？我们想一想，要把尽可能多的流量退回去，那么我们就应该跑从汇点到源点的最大流，这个最大流就是能够从汇点向源点“退回去”的最大流量。再把之前的可行流减去这个流量，就是允许的最小流量。

比如之前的图，每一条边的剩余流量是这样的：

虽然这个图的最大流是 0，但是还会有一些其他图的最大流不是 0，所以再跑一遍是有必要的。

最后的最小流流量即为可行流流量减去最大流流量，比如这个图就是 1-0=1。

大家可以尝试去手摸一下其他样例。

正确性证明

首先，由于最大流对于所有非源汇的点流量守恒，所以可行流减去最大流也是一个可行流。

然后关于这个流是最小流我们可以反证。假设原本的可行流为 f_1，我们从 t\to s 跑出来的最大流为 f_2，但这个不是最小流，还有一个更小的流 f_3。

于是呢？我们可以把 f_1 减去 f_3 得到一个流 f_4，那么这个流必定满足以下的条件：

代码

其实非常好写，从最大流的代码改几行就过了。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
const int M = 5e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m, s, t, u[M], v[M], l[M], r[M], bal[N], ss, tt, ef, idx, id[N], rf;
struct edge { int to, w, nex; } e[M];
int head[N], tot = -1;
void adde(int u, int v, int w) {
    e[++ tot] = {v, w, head[u]};
    head[u] = tot;
    e[++ tot] = {u, 0, head[v]};
    head[v] = tot;
}
int dis[N];
queue<int> q;
bool bfs(int s) {
    memset(dis, 0, sizeof dis);
    dis[s] = 1;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = e[i].nex) {
            int v = e[i].to;
            if(e[i].w && !dis[v]) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[t] != 0;
}
int cur[N];
int dfs(int u, int flow) {
    if(u == t) return flow;
    int delta = flow;
    for(int i = cur[u]; i != -1; i = e[i].nex) {
        cur[u] = i;
        int v = e[i].to;
        if(dis[v] == dis[u] + 1 && e[i].w) {
            int f = dfs(v, min(delta, e[i].w));
            delta -= f;
            e[i].w -= f;
            e[i ^ 1].w += f;
            if(delta == 0) break;
        }
    }
    return flow - delta;
}
int mf;
void dinic() {
    mf = 0;
    while(bfs(s)) {
        memcpy(cur, head, sizeof cur);
        mf += dfs(s, INF);
    }
}
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
    cin >> n >> m >> ss >> tt;
    for(int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> l[i] >> r[i];
        adde(u[i], v[i], r[i] - l[i]);
        bal[v[i]] += l[i];
        bal[u[i]] -= l[i];
        id[i] = tot;
    }
    s = n + 1;
    t = n + 2;
    adde(tt, ss, INF);
    idx = tot;
    for(int i = 1; i <= n; i++) {
        if(bal[i] > 0) {
            adde(s, i, bal[i]);
            ef += bal[i];
        }
        if(bal[i] < 0) adde(i, t, -bal[i]);
    }
    dinic();
    if(mf < ef) cout << "N\n";
    else {
        rf = e[idx].w;
        e[idx].w = e[idx ^ 1].w = 0;
        s = tt;
        t = ss;
        dinic();
        cout << rf - mf << endl;
    }
    return 0;
}