Network flow problem of upper and lower bounds in graph theory

2020/12/09

无源汇上下界可行流:

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

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

输入格式:

第一行包含两个整数 \(n\) 和 \(m\)。

接下来 \(m\) 行,每行包含四个整数 \(a,b,c,d\) 表示点 \(a\) 和 \(b\) 之间存在一条有向边,该边的流量下界为 \(c\),流量上界为 \(d\)。点编号从 \(1\) 到 \(n\)。

输出格式:如果存在可行方案,则第一行输出 \(YES\),接下来 \(m\) 行,每行输出一个整数,其中第 \(i\) 行的整数表示输入的第 \(i\) 条边的流量。

如果不存在可行方案,直接输出一行 \(NO\)。如果可行方案不唯一,则输出任意一种方案即可。

数据范围:

\(1 ≤ n ≤ 200\),

\(1 ≤ m ≤ 10200\),

\(1 ≤ a, b ≤ n\),

\(0 ≤ c ≤ d ≤ 10000\)

时/空限制:\(1s / 64MB\)

输入样例1:

4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

输出样例1:

YES
1
2
3
2
1
1

输入样例2:

4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

输出样例2:

NO

思路:

假设每条边流量上界是 \(cu\) 下界是 \(cr\)。建立新图,流量下界是 \(0\),新的上界是 \(cu - cr\),边上的流量也减去 \(cr\) 这样就转化为只有上界的可行流但是对于一个点,出边的流量减去和入边的流量减去的不是同一个值,就不一定满足流量守恒, 所以建立源点 \(S\),对于每个点,根据流入流出总量向汇点和源点连边,所有出边流量和所有入边流量求和对比,采取多退少补, 用 c入c出 代表新图中该点相比原来的守恒情况,“少进来”的流量和“少出去的流量”。

如果 c入 \(>\) c出 ,也就是少进来的更多,那么就要用源点来补充,反之就是少出去的更多,需要向汇点连边流出多余的,代码维护数组 \(A[]\) 记录每个点的 c入 减去 c出 的值,以正负来决定向源点还是汇点连边, 这样就满足了流量守恒,可以用常规的下界为 \(0\) 的最大流解决。

定理:

新图的一个最大流,对应原图的一个可行流。

因为连边的时候,采取了多退少补的策略, 而且源点向一个点连的边,既是容量也是流量,而且这个少补一定要满足,所以源点的出边必定满流, 所以只有当新图是最大流,对应的才是原图的一个上下界限制的可行流。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 210, M = (10200 + N) * 2, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], ne[M], idx, f[M], l[M]; //l记录下界
int q[N], d[N], cur[N];
int A[N]; //记录每个点的入边流量和和出边流量和的差(正负)

void add(int a, int b, int c, int d) {
    e[idx] = b, f[idx] = d - c, l[idx] = c,  ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++; //反向边下界用不到
}

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

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

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

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 a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d);
        A[a] -= c, A[b] += c; //同时更新该点的出入流量总和情况 用于后边处理
    }

    int tot = 0; //源点到所有点的连边的流量之和 判断满流
    for (int i = 1; i <= n; i++)
        if (A[i] > 0) add(S, i, 0, A[i]), tot += A[i]; //少流入的更多,源点补充流出
        else if (A[i] < 0) add(i, T, 0, -A[i]); //少流出的更多 多余的向汇点流去

    if (dinic() != tot) puts("NO");
    else {
        puts("YES");
        for (int i = 0; i < m * 2; i += 2)
            printf("%d\n", f[i ^ 1] + l[i]); //最后要加上减去的下界 此时的f记录的是残留图
        //原图中的流量 是此时残留图的反向边的权值
    }

    return 0;
}

 

有源汇上下界最大(小)流:

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

给定源点 \(S\) 和汇点 \(T\),求源点到汇点的最大流。

输入格式:

第一行包含四个整数 \(n,m,S,T\)。

接下来 \(m\) 行,每行包含四个整数 \(a,b,c,d\) 表示点 \(a\) 和 \(b\) 之间存在一条有向边,该边的流量下界为 \(c\),流量上界为 \(d\),点编号从 \(1\) 到 \(n\)。

输出格式:

输出一个整数表示最大流。如果无解,则输出 \(No \ Solution\)。

数据范围:

\(1 ≤ n ≤ 202\),

\(1 ≤ m ≤ 9999\),

\(1 ≤ a, b ≤ n\),

\(0 ≤ c ≤ d ≤ 10^5\)

时/空限制:\(1s / 64MB\)

输入样例:

10 15 9 10
9 1 17 18
9 2 12 13
9 3 11 12
1 5 3 4
1 6 6 7
1 7 7 8
2 5 9 10
2 6 2 3
2 7 0 1
3 5 3 4
3 6 1 2
3 7 6 7
5 10 16 17
6 10 10 11
7 10 14 15

输出样例:

43

思路:

先将源点 \(s\) 和汇点 \(t\) 连边,这样就是无源汇的图,然后添加新的 \(S\) 和 \(T\),边权改为减去下界,在新图上求最大流(满流) 这样就是原图的一个可行流,接着去掉原来加的 \(s\) 到 \(t\) 的边,然后从 \(s\) 开始到 \(t\), \(Dinic\) 求一遍最大流,最开始没有 \(Dinic\) 时候 \(s \rightarrow t\) 新边的流量加上 \(Dinic\) 求出的新的最大流流量,就是原图的有源汇最大流,因为新图的 \(s\) 和 \(t\) 都是中间节点,不保存流量,只需要加上加的新边的里面的流量,也就是残留网络里面反向边 \(t \rightarrow s\)的权值。

或者也可以解释为:没有 \(Dinic\) 的时候,此时 \(S \rightarrow T\) 满流状态时候 \(s \rightarrow t\) 图的所有流量就是新加的 \(t \rightarrow s\) 边的剩余流量,因为 \(s \rightarrow t\) 图是流量守恒 终点到起点的流量就是全图的流量。

代码:

#include <bits/stdc++.h>
using namespace std;

// 边数是点数+题目的边数 然后总体*2 因为新的S和T要向所有点连边维持流量守恒
const int N = 210, M = (N + 10010) * 2;
const int INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], ne[M], f[M]; //f是残留网络权值
int idx, q[N], d[N], cur[N], A[N]; //A是入边流量和减去出边流量和 cur当前弧优化

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

bool bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int ver = e[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1; //层数
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit) { //当前u 从S到u最大的可增加流量是limit
    if (u == T) return limit;
    int flow = 0; //从当前点往后流的流量最多是多少
    for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {
        cur[u] = i; //当前搜的弧
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i]) { //只搜下一层的点 防止环的干扰
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1; //当前边到终点没有增广路 就层数设为-1,之后不会再搜到了
            f[i] -= t, f[i ^ 1] += t, flow += t; //存在增广路 就更新残留网络
        }
    }
    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs())  //bfs同时建立分层图 以及返回是否有增广路
        while (flow = find(S, INF)) r += flow; //所有能够增广的流量累加

    return r;
}

int main() {
    int s, t; //题目给定的源点汇点 S T 为新加
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(h, -1, sizeof h);
    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;
    }

    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (A[i] > 0) add(S, i, A[i]), tot += A[i];
        else if (A[i] < 0) add(i, T, -A[i]);
    add(t, s, INF); //加新边 构成无源汇图
    if (dinic() < tot) puts("No Solution"); //没有满流 无解
    else {
        int res = f[idx - 1]; //加上新加的边的反向边的残余流量 然后去掉
        S = s, T = t;//直接改变源汇点 就是相当于去掉了S T还有其余的边

        f[idx - 1] = f[idx - 2] = 0; //删去新加的边 新边是最后加的 idx就是最后的2个(正反向边)
        printf("%d\n", res + dinic());
    }
    return 0;
}