网络流最大流

$$\huge 无源汇上下界可行流$$

$问题描述$

$给定一个包含 n 个点 m 条边的有向图，每条边都有一个流量下界和流量上界。$

$求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。$

$输出$

$对于每条边，输出它的流量$

$分析$

$普通的最大流只能解决下界为0的图$

$对于给定的图G = (V,E)$

$\forall e \in E , 将e的上下界限制 l_e \leq f_e \leq u_e , 转化成 0 \leq f_e - l_e \leq u_e - l_e$

$转化后有新图G’ = (V,E’)$

$\forall v \in V$

$从其他点流向v的流量为 \sum_{(u,v)}f_{(u,v)} - l_{(u,v)}$

$从v流向其他点的流量为 \sum_{(v,u)}f_{(v,u)} - l_{(v,u)}$

$建立源点S和汇点T$

$设C=\sum_{(u,v)} l_{(u,v)} - \sum_{(v,u)}l_{(v,u)}$

$若C>0,从S向v连一条权值为C的边,只要满足这条边满流,那么点v就能满足流量守恒$

$否则,从v向T连一条权值为C的边即可$

$建好图G’后从S到T求最大流$

$若最大流满足从S出发的边,以及流向T的边均满流,那么就对应了一个原图G的可行流$

$Code$

#include <bits/stdc++.h>

using namespace std;

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

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

void add(int u, int v, int w, int low)
{
    e[idx] = v, c[idx] = w, L[idx] = low, 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])
            {
                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])
        {
            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()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n + 1;

    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int u, v, low, up;
        scanf("%d%d%d%d", &u, &v, &low, &up);
        add(u, v, up - low, 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], 0), C += g[i];
        else add(i, T, -g[i], 0);

    if (dinic() != C)puts("NO");
    else
    {
        puts("YES");
        for (int i = 0; i < m * 2; i += 2)
            printf("%d\n", L[i] + c[i ^ 1]);
    }

    return 0;
}