wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

图论

图的连通性

有向图的强连通分量

无向图的割点割边和双连通分量

流和匹配

最大流

最大流的一些应用

最小割

费用流

带上下界的网络流

图论杂项

最大团搜索算法

树上问题

kruskal重构树

kruskal重构树的一些问题

最短路

差分约束

[[ item.c ]]

带上下界的网络流

## 无源汇上下界可行流
现在对于流网络，每条边有一条流量上界和下界
求一种可行方案，使得所有点满足流量守恒的前提下，同时满足流量限制

> 上下界流量预处理

假设说对于边$$c_l \leqslant f \leqslant c_u$$，首先可以令$$0 \leqslant f-c_l \leqslant c_u - c_l$$
这样每一条边$$(x, v)$$的流量$$-=c_l(x, v)$$

假设说对于点$$x$$，流经它的流量要守恒
```math
|f_x| = \sum_v f(x, v) - \sum_v f(v, x) = 0
```
令流量的变化量，$$|df_x| = -\delta(x, v) - (-\delta(v, x)) = -(\delta(x, v) - \delta(v, x))$$
其中$$\delta(x, v) = \sum_v c_l(x, v)$$

> 考虑每个节点$$x$$的流量变化

令实际的流量$$f^\*\_x = f\_x - (\delta(x, v) - \delta(v, x))$$，令$$dx = \delta(x, v) - \delta(v, x)$$
不论如何，上下界做一个变换之后，新的流量就是$$f^\* = f - dx$$
对每个点定义**亏损（或者说需求）**是$$-dx$$

1）如果$$dx > 0$$，那么意味着流网络缺少（或者说**需求**）$$|dx|$$的流量
建一个源点，并且$$f(s, x)$$连流量是$$|dx|$$的边

2）如果$$dx < 0$$，那么意味着流网络有剩余（或者说**供应**）$$|dx|$$的流量
建一个汇点，$$f(x, t)$$连流量是$$|dx|$$的边

跑一遍`dinic`，可行流 = 最大流 = $$\sum_x dx$$（即每个点的需求之和）

> 算法实现

```bash
void solve(int cas) {
    int n, m;
    cin >> n >> m;

int N = n + 5;
    int s = N - 2, t = N - 1;

maxflow<i64> g(N);
    vector<i64> dx(n+5, 0);

vector<i64> lo(m);

for (int i = 0; i < m; i++) {
        int x, y, c, d;
        cin >> x >> y >> c >> d;

g.addEdge(x, y, d - c);
        dx[x] -= c, dx[y] += c;

lo[i] = c;
    }

i64 supply = 0;
    for (int x = 1; x <= n; x++) {
        if (dx[x] >= 0) g.addEdge(s, x, dx[x]), supply += dx[x];
        else g.addEdge(x, t, llabs(dx[x]));
    }

auto flow = g.dinic(s, t);

if (flow != supply) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";

auto edges = g.edges();

for (int i = 0; i < m; i++) {
        auto res = edges[i].flow + lo[i];
        cout << res << "\n";
    }
}
```

## 有源汇上下界最大流
同样一个流网络，每条边有流量下界和上界，给定源点$$s$$和汇点$$t$$，求最大流

**算法分析**
考虑将原网络变成一个**循环流**，只需要建边$$(t\to s, +\infty)$$即可
**循环流**是处处守恒的，那么问题就转化成**无源汇上下界可行流**问题
用之前的方法解决，再引入一个**超级源`S`和超级汇`T`**，每个点引入供应和需求$$dx_x$$
按**无源汇上下界可行流**来解决

> 变成循环流之后，可以求出原问题的一个**可行流**

如果$$S \to T$$的最大流$$\neq supply$$，不等于流网络的总的供应，无解

如果有解，原问题的一个可行流，**等于循环流中**$$t \to s$$**实际流了多少**，假设说是`flow`
（这个可行流的大小，很容易通过$$t \to s$$的**反向边**流量求出来）

那么我们可以知道，原问题的**最大流大小至少应该**$$\geqslant flow$$
而在**有超级源汇的新图**中，因为有$$t \to s$$这条边的流量守恒的限制，我们不能继续增广下去

现在考虑**断开**$$t \to s$$这条边，即将其**流量上限**设置为`0`
**解除限制后**，看看从$$s \to t$$还能不能继续增广即可

> 算法设计

1）考虑$$t \to s$$连一条$$+\infty$$的边变成循环流，其余按无源汇可行流处理，建一个超级源$$S$$和超级汇$$T$$
2）跑一遍$$(S, T)$$的**最大流**，最大流$$\neq$$`总供应 supply`的话，**无解**
3）否则，最大流的大小至少应该是`flow = (s -> t) 反向边实际流的流量`
断开$$(t \to s)$$的边，流量上限设为`0`，`flow += dinic(s, t)`再看一下最多能增广多少

```bash
void solve(int cas) {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    
    int N = n + 10;
    int S = N - 2, T = N - 1;
    maxflow<i64> g(N);

vector<i64> dx(n+5, 0);
    for (int i = 0; i < m; i++) {
        int x, y, c, d;
        cin >> x >> y >> c >> d;
        g.addEdge(x, y, d - c);
        dx[x] -= c, dx[y] += c;
    }

i64 supply = 0;
    for (int x = 1; x <= n; x++) {
        if (dx[x] >= 0) g.addEdge(S, x, dx[x]), supply += dx[x];
        else g.addEdge(x, T, llabs(dx[x]));
    }
    g.addEdge(t, s, inf<i64>);

i64 flow = g.dinic(S, T);
    if (flow != supply) {
        cout << "No Solution\n";
        return;
    }
    flow = g.e.back().cap;
    for (auto &e : g.e | views::drop(g.e.size()-2)) {
        e.cap = 0;
    }

flow += g.dinic(s, t);
    cout << flow << "\n";
}
```

## 有源汇上下界最小流
给定一个流网络，每条边有流量上界和下界，给定源点和汇点$$s, t$$，求最小流

**算法分析**
> 可以按照之前的方法，先将原流网络变成**循环流**

这样建立超级源和超级汇$$S, T$$，如果此时的最大流$$\neq$$`总供应 supply`的话，无解

> 否则，求出的`flow`是一个可行流，还能不能继续减小呢？

注意到，执行完`dinic(S, T)`之后，图中的流量已经满足了所有边的下界，是一个可行流
包含两种可以调整的容量
1）正向边，容量是$$d - c$$，表示还可以继续增广的流量
2）反向边，容量为**已经流过的流量**，也即**可以撤销的流量**

此时断开$$t \to s$$我们人为添加的边（对应的正向边反向边的流量上限设置成`0`）
然后**跑`dinic(t, s)`**，此时算法**沿着反向边找增广路**，把流量从$$t$$**撤销回**$$s$$

这样`flow - dinic(t, s)`就对应最小流

> 算法实现

```bash
// 有源汇上下界最小流
void solve(int cas) {
    maxflow<i64> g(N);
    // 加边，0 <= f <= d - c，同时计算变化量 dx[x]
    vector<i64> dx(n+5, 0);
    for (int i = 0; i < m; i++) {
        int x, y, c, d;
        cin >> x >> y >> c >> d;

g.addEdge(x, y, d - c);
        dx[x] -= c, dx[y] += c;
    }

i64 supply = 0;
    for (int x = 1; x <= n; x++) {
        if (dx[x] > 0) supply += dx[x], g.addEdge(S, x, dx[x]);
        else if (dx[x] < 0) g.addEdge(x, T, llabs(dx[x]));
    }
    // 变成循环流
    g.addEdge(t, s, inf<i64>);

auto flow = g.dinic(S, T);
    // flow != 供应，无解
    if (flow != supply) {
        cout << "No Solution\n";
        return;
    }
    // flow 从 t -> s 反向边的流量上限，代表原图的一个可行流
    // 断开 t -> s 这条本来不存在的边
    flow = g.e.back().cap;
    for (auto &e : g.e | views::drop(g.e.size() - 2)) {
        e.cap = 0;
    }
    // 从 t -> s 的最大流，表示可以撤销多少流量，减去最多可以撤销的量，就是最小流
    auto df = g.dinic(t, s);
    cout << flow - df << "\n";
}
```

看完文章有啥想法

算法小站

wiki 主题

图论

带上下界的网络流

目录