「Note」有源汇有上下界最小流

Posted on Edited on

网上的模板乱七八糟的，找的的两种 $\mathrm{reliable}$ 的版本

$\mathcal{Link}$

link

$\mathcal{Sol}$

具体的证明不写了，主要是网上对于这种题的写法都不一样。重新理一遍思路。
有些东西或许是错的，如果有疑问的可以留言。

约定: $nowst$ 和 $nowed$ 表示原图指定的 源/汇 点， $st$ 和 $ed$ 表示建的虚点。

$\mathcal{Step \ 1}$

对于原图进行建边 Connect(u, v, lower, upper)
统计每个点可浮动的流量 balance[i]

$\mathcal{Step \ 2}$
  • case 1 balance[i] > 0 则 Connect(i, ed, balance[i])
  • case 2 balance[i] < 0 则 Connect(st, i, -balance[i])
    $\mathcal{Step \ 3}$
    从这一步开始就很神奇了。。。
    $\mathcal{Way \ 1}$
  • 直接Connect(nowed, nowst, 0, INF)，以$st$为源，$ed$为汇做一遍最大流。
  • 以$nowed$为源，$nowst$为汇做一遍最大流 （退流）
  • 用 $ans$ 累加上面左右最大流的和，答案是$INF - ans$ (反向边)

正常人的写法。
其实就是退流
思想是将残量网络中不需要的流退掉，将最大流与可行流相加即可（类似于有源汇上下界最大流）。

$\mathcal{Way \ 2}$
  • 以$st$为源，$ed$为汇做一遍最大流
  • Connect(nowed, nowst, 0, INF)
  • 以$st$为源，$ed$为汇做一遍最大流
  • 答案是 $$ 的反向边现存流量

这就很神奇了。
我似乎没有看到退流，但是代码写起来令人心情愉悦。
并且没有把 源汇 和 虚源汇写错的风险。

问题是为什么是对的。。。
@FlowerDream 需要您透彻的讲解，似乎机房里就您比较懂了。

$\mathcal{Code}$

$mathcal{Way \ 1}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 5e5 + 5;
const int INF = 1e18;

int n, m, sum, ans, tmp, nowst, nowed, balance[MAXN], d[MAXN], cur[MAXN], base[MAXM];
int st, ed, tot = 1, head[MAXN], edge[MAXM], nxt[MAXM], ver[MAXM];
queue<int> q;

void AddEdge(int u, int v, int c) {
    ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
    ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs(int st) {
    
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[st] = 1, q.push(st), cur[st] = head[st];

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i];
            if (!edge[i] || d[v]) continue;
            d[v] = d[u] + 1, cur[v] = head[v];
            q.push(v);
            if (v == ed) return true;
        }
    }

    return false;

}

int dinic(int u, int flow) {

    if (u == ed) return flow;

    int res = flow;
    for (int i = cur[u]; i && res; i = nxt[i]) {
        int v = ver[i];
        if (!edge[i] || d[v] != d[u] + 1) continue;
        int k = dinic(v, min(res, edge[i]));
        if (!k) d[v] = 0;
        edge[i] -= k, edge[i ^ 1] += k, res -= k;
        cur[u] = i;
    }

    return flow - res;

}

signed main() {

    // freopen("7.in", "r", stdin);

    scanf("%lld %lld %lld %lld", &n, &m, &nowst, &nowed);
    
    st = n + 1, ed = n + 2;
    for (int i = 1, u, v, lower, upper; i <= m; i++) {
        scanf("%lld %lld %lld %lld", &u, &v, &lower, &upper);
        balance[u] += lower, balance[v] -= lower, base[i] = lower;
        AddEdge(u, v, upper - lower);
    }

    for (int i = 1; i <= n; i++) {
        if (balance[i] > 0) {
            sum += balance[i];
            AddEdge(i, ed, balance[i]);
        } else {
            AddEdge(st, i, -balance[i]);
        }
    }
    AddEdge(nowed, nowst, INF);

    while (bfs(st)) {
        while ((tmp = dinic(st, INF))) ans += tmp;
    }

    if (ans < sum) {
        printf("please go home to sleep\n");
    } else {
        st = nowed, ed = nowst, ans = 0;
        // printf("%lld\n", ans);
        while (bfs(st)) {
            while ((tmp = dinic(st, INF))) ans += tmp;
        }
        printf("%lld\n", INF - ans);
    }

    return 0;
}
$\mathcal{Way \ 2}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 5e5 + 5;
const int INF = 1e18;

int n, m, sum, ans, tmp, nowst, nowed, balance[MAXN], d[MAXN], cur[MAXN], base[MAXM];
int st, ed, tot = 1, head[MAXN], edge[MAXM], nxt[MAXM], ver[MAXM];
queue<int> q;

void AddEdge(int u, int v, int c) {
    ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
    ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

void Connect(int u, int v, int lower, int upper) {
    AddEdge(u, v, upper - lower);
    balance[u] += lower, balance[v] -= lower;
}

bool bfs(int st) {
    
    while (!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[st] = 1, q.push(st), cur[st] = head[st];

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i];
            if (!edge[i] || d[v]) continue;
            d[v] = d[u] + 1, cur[v] = head[v];
            q.push(v);
            if (v == ed) return true;
        }
    }

    return false;

}

int dinic(int u, int flow) {

    if (u == ed) return flow;

    int res = flow;
    for (int i = cur[u]; i && res; i = nxt[i]) {
        int v = ver[i];
        if (!edge[i] || d[v] != d[u] + 1) continue;
        int k = dinic(v, min(res, edge[i]));
        if (!k) d[v] = 0;
        edge[i] -= k, edge[i ^ 1] += k, res -= k;
        cur[u] = i;
    }

    return flow - res;

}

signed main() {

    // freopen("7.in", "r", stdin);

    scanf("%lld %lld %lld %lld", &n, &m, &nowst, &nowed);
    
    st = n + 1, ed = n + 2;
    for (int i = 1, u, v, lower, upper; i <= m; i++) {
        scanf("%lld %lld %lld %lld", &u, &v, &lower, &upper);
        Connect(u, v, lower, upper);
    }

    for (int i = 1; i <= n; i++) {
        if (balance[i] > 0) {
            sum += balance[i];
            AddEdge(i, ed, balance[i]);
        } else {
            AddEdge(st, i, -balance[i]);
        }
    }

    while (bfs(st)) while ((tmp = dinic(st, INF))) ans += tmp;
    Connect(nowed, nowst, 0, INF);
    while (bfs(st)) while ((tmp = dinic(st, INF))) ans += tmp;

    if (ans < sum) {
        printf("please go home to sleep\n");
    } else {
        printf("%d\n", edge[tot]);
    }

    return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」