$网络流算法$ 、 $网络流最大流$

$$\huge {有源汇上下界最大流}$$

$问题描述$

$给定一个包含 n 个点 m 条边的有向图，以及源点S和汇点T。$

$每条边都有一个流量下界和流量上界。$

$求源点到汇点的最大流量。$

$分析$

像 $无源汇上下界可行流$ 一样

$建立新的源点S’，汇点T’,从T到S建立一条权值为inf的边,使得S和T满足流量守恒$

$对于每个点u,从S’连向u或从u连向T’$

$只要满足从S’出发的所有边都满流,那么就是原图G中的一个可行流$

$从S’出发做一遍最大流,记为f,若从S’出发的边没有满流,则无解$

$若满流了,删去T到S权值为inf的边$

$在残留网络Gf中求S到T的最大流,记为f’$

$即答案为f + f’$

$证明$

$由于f在原图G中对应了一个可行流$

$而f’中都不涉及从S’出来的边,以及流向T’的边$

$所以f + f’也一定对应了原图G的可行流$

$在f + f’中,去除从S’出来的边,以及流向T’的边$

$由于流量可以退还,所以这一定是G中的最大流$

$证毕$

$Code$

#include <bits/stdc++.h>

using namespace std;

const int N = 210, M = 20410, inf = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], c[M], ne[M], idx;
int q[N], g[N], dep[N], cur[N];


void add(int u, int v, int w)
{
    e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}

bool bfs()
{
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dep[j] == -1 && c[i] > 0)
            {
                dep[j] = dep[t] + 1;
                cur[j] = h[j];
                if (j == T)return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T)return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if (dep[j] == dep[u] + 1 && c[i] > 0)
        {
            int t = find(j, min(c[i], limit - flow));
            if (!t)dep[j] = -1;
            c[i] -= t, c[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while (bfs()) while (flow = find(S, inf)) res += flow;
    return res;
}

int main()
{
    int s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    S = 0, T = n + 1;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int u, v, low, up;
        scanf("%d%d%d%d", &u, &v, &low, &up);
        add(u, v, up - low);
        g[u] -= low, g[v] += low;
    }

    int C = 0;
    for (int i = 1; i <= n; i ++ )
        if (g[i] > 0)add(S, i, g[i]), C += g[i];
        else if (g[i] < 0)add(i, T, -g[i]);

    add(t, s, inf);
    if (dinic() != C)puts("No Solution");
    else
    {
        int res = c[idx - 1];
        S = s, T = t;
        c[idx - 1] = c[idx - 2] = 0;
        printf("%d", res + dinic());
    }

    return 0;
}