题解：P14579 【模板】有源汇上下界最大流

· · 题解

（画图好累啊）

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。

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

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];//更新节点流量差
    }
    s = n + 1;
    t = n + 2;//建立新的超级源点和超级汇点
    adde(tt, ss, INF);//无源汇转有源汇
    idx = tot;//记录一下这一条边的id，之后要删掉
    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 = ss;
        t = tt;//更新源点和汇点为题目要求的源汇
        dinic();//再跑一遍最大流
        cout << rf + mf << endl;//流量为两次流量之和
    }
    return 0;
}