无源汇上下界可行流问题

解题思路

按照最大流问题的基本解题思路，我们同样需要构建一个流网络。

这个流网络中的可行流需要满足流量守恒和容量限制，其中容量限制不再只有一个上界了，还加了一个下界限制。

假设有一个流网络 $G$，存在任意一个可行流 $f$，不存在源点和汇点，我们需要将它转化成一个新的流网络 $G’$，存在任意一个新的可行流 $f’$，$G’$ 中存在源点和汇点，且只有上界没有下界。

对于流网络 $G$ 的可行流 $f$ 中的某一条边 $(u, v)$，容量上界记为 $C_u(u, v)$，容量下界记为 $C_l(u, v)$，当前流量记为 $f(u, v)$。当前满足 $C_l(u, v) \leq f(u, v) \leq C_u(u, v)$。

我们现在需要将 $G$ 转化成 $G’$，使得可行流 $f’$ 中任意一条边 $(u, v)$ 满足 $0 \leq f’(u, v) \leq C’(u, v)$。

这里可以想到一个直观的方法，就是把原等式的每一项都减去 $C_l(u, v)$，那么原等式就变成 $0 \leq f(u, v) - C_l(u, v) \leq C_u(u, v) - C_l(u, v)$。这就是我们转化的新流网络里可行流的容量限制，且满足只有上界没有下界的要求。

因此转化成新流网络的步骤就是，设置新流网络中边的容量 $C’(u, v)$ 为 $C_u(u, v) - C_l(u, v)$，而 $f(u, v) - C_l(u, v)$ 就是原流网络中的可行流变到新流网络里之后，新可行流中边的流量。根据转化，它是必然满足容量限制的。

虽然新可行流满足容量限制，但是不一定满足流量守恒，因为对于某一个点 $x$，对于进入点 $x$ 的每条边的流量，都需要减去 $C_l(u, v)$，因此所有进入点 $x$ 的总流量相比原流网络会少 $\sum_{v \in V} (v, x)$，记为 $C_入$，那么新的进入点 $x$ 的总流量就是原总流量 $- C_入$。对于从点 $x$ 出去的每条边的流量，同样需要减去 $C_l(u, v)$，因此所有从点 $x$ 出去的总流量相比原网络会少 $\sum_{v \in V} (x, v)$，记为 $C_出$，那么新的从点 $x$ 出去的总流量就是原总流量 $- C_出$。

对于原流网络，点 $x$ 是一定满足进来的流量等于出去的流量的。但是由于新流网络中每条边都需要减去一个固定的量，假设进入点 $x$ 的边有 $a$ 条，从点 $x$ 出去的边有 $b$ 条，如果 $a > b$，那么就会导致 $C_入 > C_出$，就不满足流量守恒了。

怎么解决流量不守恒呢，可以发现现在进入的流量会比出去的流量少 $C_入 - C_出$，我们只需要把少进入的流量补上，只需要从源点向点 $x$ 连一条容量为 $C_入 - C_出$ 的边。反之如果 $C_入 < C_出$，反过来需要从点 $x$ 向汇点连一条容量为 $C_出 - C_入$ 的边。这样就满足流量守恒了。

注意这里还有一点，就是补完流量守恒之后，我们必须要保证这些补进来的边必须都是满流，才是流量守恒，因此在原图中的可行流其实对应的是新图中的最大流。

综上，得出原流网络中可行流的集合与新流网络中最大流的集合是一一对应的。那么原流网络中是否存在可行流就等价于新流网络中是否存在最大流，即判断从源点出去的边是否满流。

如果新图中存在最大流，说明原图中存在可行流，我们只需要将新图的最大流通过逆操作转化回原图的可行流就行了，转化方式就是每条边的流量加上 $C_l(u, v)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = 20810, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], w[M], l[M], e[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
int A[N]; //a[i] 表示点i所有入边的容量下界之和 - 点i所有出边的容量下界之和

void add(int a, int b, int c, int d) //添加边
{
    e[idx] = b, w[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //搜索从 u 节点往终点传输的最大流量，flow 表示当前传输到 u 节点的流量
{
    if(u == T) return flow;

    int rest = flow; //记录剩余没有往下传输的流量
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(w[i] && d[j] == d[u] + 1)
        {
            int k = find(j, min(rest, w[i]));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //dinic算法求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    S = 0, T = n + 1; //源点、汇点
    //构建 G'
    for(int i = 0; i < m; i++)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d); //添加边
        A[a] -= c, A[b] += c; //点a出去了c的容量下界，点b进来了c的容量下界
    }

    int sum = 0; //记录从源点出发到每个点的流量之和，用于判断是否满流
    for(int i = 1; i <= n; i++)
        if(A[i] > 0) add(S, i, 0, A[i]), sum += A[i]; //C入 > C出
        else if(A[i] < 0) add(i, T, 0, -A[i]); //C入 < C出

    if(dinic() != sum) puts("NO"); //如果求的最大流不是满流的，说明无解
    else //否则有解
    {
        puts("YES");

        //输出方案，即原图的可行流的流量
        for(int i = 0; i < m * 2; i += 2)
            printf("%d\n", w[i ^ 1] + l[i]); //原图边的流量是残量网络反向边的容量，再加上容量下界
    }

    return 0;
}