有源汇上下界最小流问题

解题思路

本题已经在有源汇上下界最大流问题中整个推导过了，两个问题是几乎一模一样的，原理就是将 $f$ 和 $f_{0~s->t}’ + f_{s->t}’$ 对应起来，而 $f$ 的最小流就是 $f_{0~s->t}’ + f_{s->t}’$ 的最小流，由于 $f_{0~s->t}$ 的流量固定，所以要让 $f_{s->t}’$ 尽可能小，对应的就是让从 $t$ 到 $s$ 的流量尽可能大，因此求出从 $t$ 到 $s$ 的最大流，就能求出从 $s$ 到 $t$ 的最小流。由于 $f_{s, t}’ = -f_{t, s}’$，所以 $min~f_{s, t}’ = -max~f_{t, s}’$，最终得出原图的最小流为 $f_{0~s->t}’ - f_{t->s}’$。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50010, M = (N + 125003) * 2 + 10, INF = 2147483647;

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

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[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
{
    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(d[j] == d[u] + 1 && w[i])
        {
            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()
{
    int s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);

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

    //建立 G'
    S = 0, T = n + 1; //虚拟源点、汇点
    while(m--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, d - c); //添加边
        A[a] -= c, A[b] += c; //a - 出边下界容量，b + 入边下界容量
    }

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

    add(t, s, INF); //连一条从 t 到 s 容量为 INF 的边，保证所有点满足流量守恒

    if(dinic() != sum) puts("No Solution"); //不是满流，说明无解
    else //否则有解
    {
        //原图最小流 = s 到 t 的流量 + s 到 t 的最小流 = s 到 t 的流量 - t 到 s 的最大流
        int res = w[idx - 1]; //s 到 t 的流量 = 反向边的容量

        S = t, T = s; //接下来要求从 t 到 s 的最大流，重新初始化一下源点和汇点
        w[idx - 1] = w[idx - 2] = 0; //将之前加入的从 t 到 s 的虚边删掉
        printf("%d\n", res - dinic()); //输出原图最大流
    }

    return 0;
}