上下界可行流

2024-03-28 20:58:16

无源汇上下界可行流

模型描述

在流网络中，每条边的流量范围不再是\([0, c_i]\)，而是\([down_i, up_i]\)，同时还要满足流量守恒。求一个可行流。

建模

我们要想办法转变为一般的最大流问题。

考虑将容量上界和下界分别减去\(down_i\)，即可行流需满足\(0 \leq f'_i \leq up_i - down_i\)，即\(down_i \leq f'_i + down_i \leq up_i\)。

若最后存在可行流，那么流量为\(f'_i + down_i\)。问题就转化成了在一般的流网络上求\(f'_i\)的问题了。

但是，在转化成一般的网络流问题的过程中，会出现流量不守恒的情况。

原因是对于节点\(i\)，将指向\(i\)的边集设为\(In_i\)，将\(i\)指向其他节点的边集记为\(Out_i\)。有\(\sum_{j \in In_i} f_j = \sum_{j \in Out_i} f_j\)，但是不一定满足\(\sum_{j \in In_i} f_j + down_j = \sum_{j \in Out_i} f_j + down_j\)。

因此我们需要将流网络进行一定调整，设置源点\(S\)、汇点\(T\)，记每条边\(\alpha(i) = \sum_{j \in Out_i} down_j - \sum_{j \in In_i} down_j\)。

如果\(\alpha(i) > 0\)，则从\(S\)向\(i\)连一条容量是\(\alpha(i)\)的边；如果\(\alpha(i) < 0\)，则从\(i\)向\(T\)连一条容量是\(-\alpha(i)\)的边。

跑一遍最大流，如果最大流小于以\(S\)为起点的边的容量和，那么说明肯定会有流量不守恒的情况，因此 不存在可行流。反之，存在可行流。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 210, M = (N + 10200) * 2, inf = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], l[M], ne[M], idx;
int cur[N], d[N], ad[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()
{
    memset(d, -1, sizeof(d));
    queue<int> que;
    que.push(S);
    d[S] = 0, cur[S] = h[S];
    while(que.size()) {
        int t = que.front();
        que.pop();
        for(int i = h[t]; ~i; 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;
                que.push(ver);
            }
        }
    }
    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 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 res = 0, flow;
    while(bfs()) {
        while(flow = find(S, inf)) {
            res += flow;
        }
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof(h));
    S = 0, T = n + 1;
    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);
        ad[a] -= c, ad[b] += c;
    }
    int tot = 0;
    for(int i = 1; i <= n; i ++) {
        if(ad[i] > 0) add(S, i, 0, ad[i]), tot += ad[i];
        else add(i, T, 0, -ad[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]);
        }
    }
    return 0;
}

有源汇上下界可行流/最大流

模型描述

在无源汇上下界可行流问题的流网络基础上，指定了源点和汇点。求可行流/最大流。

建模

从汇点\(t\)向源点\(s\)连一条上界是\(\infty\)，下界是\(0\)的边。其他步骤同无源汇情形。

以源点为\(S\)，汇点为\(T\)，求得一个可行流的流量\(f_1\)为\(t\)到\(s\)的边的反向边。

若求最大流，那么删掉\(t\)到\(s\)的边及其反向边，以\(s\)为源点，\(t\)为汇点，再跑一遍最大流，流量记为\(f_2\)

最终结果为\(f = f_1 + f_2\)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 210, M = (N + 10000) * 2, inf = 1e8;

int n, m, S, T;
int h[N], e[M], ne[M], f[M], l[M], idx;
int cur[N], d[N], 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()
{
    memset(d, -1, sizeof(d));
    queue<int> que;
    que.push(S);
    d[S] = 0, cur[S] = h[S];
    while(que.size()) {
        int t = que.front();
        que.pop();
        for(int i = h[t]; ~i; 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;
                que.push(ver);
            }
        }
    }
    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 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 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);
    memset(h, -1, sizeof(h));
    S = 0, T = n + 1;
    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]);
    }
    add(t, s, 0, inf);
    if(tot != dinic()) puts("No Solution");
    else {
        int res = f[idx - 1];
        f[idx - 1] = f[idx - 2] = 0;
        S = s, T = t;
        printf("%d\n", res + dinic());
    }
    return 0;
}

有源汇上下界最小流

建模

在可行流的基础上，以\(t\)为源点，\(s\)为汇点，求最大流，记为\(f_2\)

最终结果为\(f = f_1 - f_2\)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 50010, M = (N + 125010) * 2, inf = 2147483647;

int n, m, S, T;
int h[N], e[M], ne[M], f[M], l[M], idx;
int cur[N], d[N], A[N];

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

bool bfs()
{
    memset(d, -1, sizeof(d));
    queue<int> que;
    que.push(S);
    d[S] = 0, cur[S] = h[S];
    while(que.size()) {
        int t = que.front();
        que.pop();
        for(int i = h[t]; ~i; 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;
                que.push(ver);
            }
        }
    }
    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 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 res = 0, flow;
    while(bfs()) {
        while(flow = find(S, inf)) {
            res += flow;
        }
    }
    return res;
}

int main()
{
    int t, s;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(h, -1, sizeof(h));
    S = 0, T = n + 1;
    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]);
    }
    add(t, s, 0, inf);
    if(tot != dinic()) puts("No Solution");
    else {
        int res = f[idx - 1];
        f[idx - 1] = f[idx - 2] = 0;
        S = t, T = s;
        printf("%d\n", res - dinic());
    }
    return 0;
}
上一篇：圆桌问题（最大流，二分图，网络流24题）


下一篇：25、邻接表：有向无环图（DAG）的判断