Advanced Network Flow (with bounds)

醉里挑灯看剑，梦回吹角连营了属于是

带上下界的网络流

我们之前接触的网络流所涉及的问题一般就局限在最大流（最小割）、费用流之类的问题，但是现在有一类对流量有所限制的网络流模型需要考虑。

假如现在对一条边$e:(u\to v)$，需要保证这条边的流量有上下界$l(e) \leq c(e) \leq u(e)$，同时需要保证除了网络流图中除了源点与汇点之外的所有中间节点流量平衡，即流入流量等于其流出流量。

没有源点汇点的上下界可行流

给你一个没有源点和汇点的流量网络，想知道有没有一种可行的分配每条边流量的方式，使得每条边的流量均满足上下界约束并保证中间节点流量平衡。

因为每条边至少都要达到$l(e)$的流量，干脆初始状态的流量就设为这个下界。但是全部由下界所建成的流量网络明显做不到流量平衡，有的流入大于流出，也有的流出大于流入。

为了解决这个问题，我们加边，在初始流的基础上添加附加流。

设$d(i)$为在初始流量网络中，编号为$i$的中间节点流入量与流出量之差，即$d(i) = f_{i_0}(u) - f_{o_0}(u)$。明显大于0就说明流入大于流出，小于0说明流出大于流入，等于0就平衡啦。

在流量不平衡的节点$u$要想最终构建成流量平衡，那就要保证

$$f_{i_0}(u) + f_{i_1}(u) = f_{o_0}(u) + f_{o_1}(u)$$

• 当$d(i) >0$, $f_{o_1}(u) = f_{i_1}(u) + d(i)$，附加流流出量比流入量更多，我们从没有源点汇点的流量网络中是没法改变的，办法是建立超级源点，从超级源点给节点$u$一个$d(i)$的流量作为补偿。
• 当$d(i) <0$, $f_{i_1}(u) = f_{o_1}(u) + (-d(i))$，附加流流入量比流出量更多，我们同样没法从内部改变，于是对应地建立超级汇点，从节点$u$到超级汇点给一个$-d(i)$的流量作为补偿。

从世界之外，我们取得否定世界的力量

但是问题是引入了补偿之后怎么确保方案可行？其实只需要判断一下从超级源点连出去的所有的附加边都能够满流即可，因为一个节点的附加边满流恰好说明该节点流量平衡。

所以我们最后从超级源点为起点，跑最大流算法，只要确保所有附加边满流即可得到一个可行流。我们这里求得的可行流是针对满足下界的可行流。

例题：LOJ115

struct Edge {
    int next, to, capacity, idx;
} e[maxm << 2];
int head[maxn];
int tot = 1;

int d[maxn];
int low[maxm];
int ans[maxm];

int h[maxn];

int n, m, S, T;

void link(int u, int v, int lower, int upper, int idx) {
    e[++tot] = {head[u], v, upper - lower, idx};
    head[u] = tot;
    e[++tot] = {head[v], u, 0, 0};
    head[v] = tot;
}

bool bfs() {
    memset(h, 0, sizeof(h));
    std::queue<int> q;
    q.push(S); h[S] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (!h[v] && e[i].capacity > 0) {
                h[v] = h[u] + 1;
                q.push(v);
            }
        }
    }
    return h[T];
}

int maxflow(int u, int flow) {
    if (u == T) return flow;
    int s = 0;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (h[v] == h[u] + 1 && e[i].capacity > 0 && s < flow) {
            int t = maxflow(v, std::min(e[i].capacity, flow - s));
            e[i].capacity -= t; e[i ^ 1].capacity += t;
            s += t;
        }
    }
    if (s == 0) h[u] = 0;
    return s;
}

void dinic() {
    while (bfs()) {
        int t = maxflow(S, 0x7fffffff);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    int u, v, lower, upper;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d %d", &u, &v, &lower, &upper);
        link(u, v, lower, upper, i);
        d[u] -= lower; d[v] += lower; 
        low[i] = lower;
    }
    S = n + 1;
    T = S + 1;
    int temp_tot = tot;
    for (int i = 1; i <= n; i++) {
        if (d[i] > 0) {
            link(S, i, 0, d[i], 0);
        } else if (d[i] < 0) {
            link(i, T, d[i], 0, 0);
        }
    }
    dinic();
    
    bool flag = true;
    for (int i = head[S]; i; i = e[i].next) {
        if (e[i].capacity > 0) {
            flag = false;
            break;
        }
    }
    
    if (flag) {
        for (int i = 2; i <= temp_tot; i += 2) {
            ans[e[i].idx] = e[i ^ 1].capacity;
        } 
        printf("YES\n");
        for (int i = 1; i <= m; i++) {
            printf("%d\n", ans[i] + low[i]);
        }
    } else {
        printf("NO\n");
    }
}

有源点汇点的上下界可行流

给定一个有源点汇点的流量网络，想要求一个所有边满足对应上下界的可行流。

我们尝试一下能不能转换为上一个我们已经知道解法的没有源点汇点的上下界可行流问题。（经典化未知为已知）

事实上真的可以，对于源点$s$和汇点$t$，我们其实可以从$t$到$s$建立一条边，下界为$0$，上界为$\infty$，原先$s$跟$t$这两个点是游离于流量平衡规则之外的，现在我们通过一个上下界无比宽广的边来约束它们，使它们遵循流量平衡规则的同时不改变原有答案。

现在已经获得了一个裸的无源点汇点的流量网络，接下来就是前面的步骤了，诸如建立超级源点和超级汇点，平衡所有中间节点的流量（包含$s$和$t$）。

从超级源点开跑最大流，判是否可行的方法还是类似。

如果判断了可行，那么$s$到$t$的可行流流量就等于$t$到$s$的附加边流量。（由流量平衡可得）

但是具体是怎么看流量大小的呢？跑完最大流之后，一条边的流量大小需要看它的伴生边的流量大小。（除非一开始就对容量已经有记录了，那就可以在原来的边上直接相减得到了）

例题

没有例题。。。

有源点汇点的上下界最大流

给定一个有源点汇点的流量网络，想要求一个所有边满足对应上下界的最大流。

我们尝试一下能不能转换为上一个我们已经知道解法的没有源点汇点的上下界可行流问题，在可行的基础上保证最大流。

事实上只要跑两次最大流就可以了。

我们通过有源点汇点的上下界可行流，通过最大流算法并验证得到一个可行方案，并查看可行流流量，这些的具体细节不再重复。

但是还没结束！从超级源点开始跑完最大流之后，原图中还有残余的自由流！我们现在需要做的是抛弃掉超级源点与超级汇和与其有关的边，然后从$s$到$t$再跑一遍最大流，两边最大流的答案相加才是最终的答案。

例题：LOJ116

int n, m, s, t;
int S, T;

struct Edge {
    int next, to, capacity, idx;
} e[maxm << 2];
int tot = 1;
int head[maxn];
int d[maxn];
int h[maxn];

void link(int u, int v, int c, int idx) {
    e[++tot] = {head[u], v, c, idx};
    head[u] = tot;
    e[++tot] = {head[v], u, 0, 0};
    head[v] = tot;
}

bool bfs() {
    memset(h, 0, sizeof(h));
    std::queue<int> q;
    q.push(S); h[S] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (!h[v] && e[i].capacity > 0) {
                h[v] = h[u] + 1;
                q.push(v);
            }
        }
    }
    return h[T];
}

int maxflow(int u, int flow) {
    if (u == T) return flow;
    int s = 0;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (h[v] == h[u] + 1 && e[i].capacity > 0 && s < flow) {
            int t = maxflow(v, std::min(e[i].capacity, flow - s));
            e[i].capacity -= t; e[i ^ 1].capacity += t;
            s += t;
        }
    }
    if (s == 0) h[u] = 0;
    return s;
}


int dinic() {
    int ans = 0;
    while (bfs()) {
        ans += maxflow(S, 0x3f3f3f3f);
    }
    return ans;
}

int main() {
    n = read(), m = read(), s = read(), t = read();
    int u, v, lower, upper;
    for (int i = 1; i <= m; i++) {
        u = read() ,v = read(), lower = read(), upper = read();
        link(u, v, upper - lower, i);
        d[u] -= lower; d[v] += lower;
    }
    S = n + 1; T = S + 1;
    for (int i = 1; i <= n; i++) {
        if (d[i] > 0) {
            link(S, i, d[i], 0);
        } else if (d[i] < 0) {
            link(i, T, -d[i], 0);
        }
    }
    link(t, s, 0x3f3f3f3f, 0);
    int sum = dinic();
    // printf("sum = %d\n", sum);

    bool flag = true;
    for (int i = head[S]; i; i = e[i].next) {
        if (e[i].capacity > 0) {
            flag = false;
            break;
        }
    }

    if (!flag) {
        printf("please go home to sleep\n");
        return 0;
    }
    // printf("%d %d %d %d\n", e[head[s]].capacity, e[head[s] ^ 1].capacity, e[head[t]].capacity, e[head[t] ^ 1].capacity);
    int ans = e[head[t] ^ 1].capacity;
    // printf("ans: %d\n", ans);
    for (int i = 2; i <= tot; i++) {
        if (e[i].idx == 0) {
            e[i].capacity = 0;
        }
    }
    head[S] = head[T] = 0;
    S = s, T = t;
    int res = dinic();
    printf("%d\n", ans + res);
    return 0;
}

有源点汇点的上下界最小流

第一个做法

同样建立在有源点汇点的上下界可行流的基础上来做。

通过那一套步骤算出可行流流量之后，我们知道残量网络里面还有自由流，我们不能拿可行流流量直接当做最小流，因为残量网络里面有一些流量是不必要的，我们可以退掉，并且只要尽可能退掉越多，我们就离最小流的答案越接近。

但是怎么退呢？这是一个好问题。

事实上我们只要反过来想就可以了，在残量网络中的反向边就是来让你反悔的，我们如果想要最大程度上地退掉流量，就可以增广反向边，即在以$t$为源点，$s$为汇点的反向流量网络上跑最大流，最大流多少我们就能退多少！

所以最终的答案就是前面求出的可行流大小减掉反向流量网络的最大流。

第二个做法

做法2：（其实我觉得做法1更容易理解）

建立超级源和超级汇之后呢。

先跑一次最大流。

然后t到s连一条无穷大的边。

再跑一次最大流。

最后的答案就是无穷大的边流过的流量。

有点难理解。

首先因为整个图满足流量平衡。

所以说t点流入的流量等于流出的流量。

那么他流出的流量只有那一条无穷大的边而已。

所以说最小流就是求那条边（无穷边）流过的流量尽量小而已。

所以说第一次流最大流的时候已经满足下界。那么满足下界能流的边已经流满。

所以残量网络剩下的最大流就会尽可能的小了。

版权声明：本文为CSDN博主「Hanks_o」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/Hanks_o/article/details/77995557

其实不好理解，建议大家还是着重理解第一种解法吧。

例题：LOJ117

懒得再写一遍第一种方法的实现了，开摆

有源点汇点的上下界最小费用流

其实建图部分的思想都是共通的，包括

• 建立超级源点与超级汇点，与原图节点连边（费用为0）
• 从$t$到$s$连容量为$\infty$，费用为0的的边

获得答案就容易的多了，只需要在超级源点处开跑最小费用最大流，并加上所有下界流量所造成的费用即是答案。

其实讲到这里，最后的这个问题反倒可以一语带过了，所以学东西还是要有层次地学好呀！

例题：洛谷P4043 支线剧情

struct Edge {
    int next, to, capacity, cost;
} e[maxm << 2];
int head[maxn];
int tot = 1;

int d[maxn];
int low[maxm];

int h[maxn];

int n, m, s, t, S, T;

int ans;

bool vis[maxn];

void link(int u, int v, int lower, int upper, int cost) {
    e[++tot] = {head[u], v, upper - lower, cost};
    head[u] = tot;
    e[++tot] = {head[v], u, 0, -cost};
    head[v] = tot;
}

bool spfa() {
    memset(h, -1, sizeof(h));
    memset(vis, false, sizeof(vis));
    std::queue<int> q;
    q.push(T); h[T] = 0; vis[T] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false;
        for (int i = head[u]; i; i = e[i].next) {
            if (!e[i ^ 1].capacity) continue;
            int v = e[i].to, c = e[i].cost;
            if (h[v] == -1 || h[v] > h[u] - c) {
                h[v] = h[u] - c;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return h[S] != -1;
}

int dfs(int u, int flow) {
    if (u == T) {
        vis[T] = true;
        return flow;
    }
    int f = 0;
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to, c = e[i].cost;
        if (h[v] == h[u] - c && e[i].capacity > 0 && !vis[v]) {
            int temp = dfs(v, std::min(flow, e[i].capacity));
            if (temp) {
                f += temp; flow -= temp;
                ans += temp * e[i].cost;
                e[i].capacity -= temp; e[i ^ 1].capacity += temp;
                if (flow == 0) return f;
            }
        }
    }
    return f;
}

int costflow() {
    int res = 0;
    while (spfa()) {
        vis[T] = true;
        while (vis[T]) {
            memset(vis, false, sizeof(vis));
            res += dfs(S, inf);
        }
    }
    return res;
}

int main() {
    n = read();
    int temp, v, tim;
    for (int u = 1; u <= n; u++) {
        temp = read();
        while (temp--) {
            v = read(), tim = read();
            link(u, v, 1, inf, tim);
            d[u]--, d[v]++;
            ans += tim;
        }
    }
    s = 1, t = n + 1;
    S = n + 2, T = n + 3;
    for (int i = 2; i <= n; i++) {
        link(i, t, 1, inf, 0);
    }
    link(t, s, 0, inf, 0);
    for (int i = 1; i <= n; i++) {
        if (d[i] > 0) {
            link(S, i, 0, d[i], 0);
        } else if (d[i] < 0) {
            link(i, T, d[i], 0, 0);
        }
    }
    costflow();
    printf("%d\n", ans);
}

References

• https://blog.csdn.net/Hanks_o/article/details/77970978
• https://blog.csdn.net/Hanks_o/article/details/77984623
• https://blog.csdn.net/Hanks_o/article/details/77995557
• https://oi-wiki.org/graph/flow/bound/