P4843 清理雪道

· · 题解

题目地址：P4843 清理雪道

上下界网络流

无源汇上下界可行流

给定 n 个点， m 条边的网络，求一个可行解，使得边 (u,v) 的流量介于 [B(u,v),C(u,v)] 之间，并且整个网络满足流量守恒。

如果把 C-B 作为容量上界， 0 作为容量下界，就是一般的网络流模型。

然而求出的实际流量为 f(u,v)+B(u,v) ，不一定满足流量守恒，需要调整。

设 inB[u]=\sum B(i,u) ， outB[u]=\sum B(u,i) ， d[u]=inB[u]-outB[u] 。

新建源汇， S 向 d>0 的点连边， d<0 的点向 T 连边，容量为相应的 d 。

在该网络上求最大流，则每条边的流量 + 下界就是原网络的一个可行流。

具体实现时，可省略 inB,outB 数组，直接在 d 数组上修改。

有源汇上下界可行流

从 T 到 S 连一条下界为 0 ，上界为 +inf 的边，把汇流入的流量转移给源流出的流量，转化为无源汇的网络，然后求解无源汇上下界可行流。

有源汇上下界最小流

两个方法：

  1. 二分答案 ans ，从 T 到 S 连一条下界为 0 ，上界为 ans 的边，转化为无源汇网络。找到最小的 ans ，使得该无源汇上下界网络有可行流。
  2. 类似有源汇上下界可行流的构图方法，但先不添加 T 到 S 的边，求一次超级源到超级汇的最大流。然后再添加一条从 T 到 S 下界为 0 ，上界为 +inf 的边，在残量网络上再求一次超级源到超级汇的最大流。流经 T 到 S 的边的流量就是最小流的值。该算法的思想是在第一步中尽可能填充循环流，以减小最小流的代价。

连边：

  3. 对每条雪道，连边 (i,j,1,+inf) 。

对网络 s-t 求有源汇上下界最小流。

这里使用方法二。

#include <bits/stdc++.h>
using namespace std;
const int N = 106, M = 2e4 + 6, inf = 1e9;
int n, s, t, S, T, d[N], ans;
int Head[N], Edge[M], Leng[M], Next[M], tot = 1;

inline void add(int x, int y, int z) {
    Edge[++tot] = y;
    Leng[tot] = z;
    Next[tot] = Head[x];
    Head[x] = tot;
    Edge[++tot] = x;
    Leng[tot] = 0;
    Next[tot] = Head[y];
    Head[y] = tot;
}

inline void ins(int x, int y, int l, int r) {
    add(x, y, r - l);
    d[x] -= l;
    d[y] += l;
}

inline bool bfs() {
    memset(d, 0, sizeof(d));
    queue<int> q;
    q.push(S);
    d[S] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = Head[x]; i; i = Next[i]) {
            int y = Edge[i], z = Leng[i];
            if (d[y] || !z) continue;
            q.push(y);
            d[y] = d[x] + 1;
            if (y == T) return 1;
        }
    }
    return 0;
}

int dinic(int x, int flow) {
    if (x == T) return flow;
    int rest = flow;
    for (int i = Head[x]; i && rest; i = Next[i]) {
        int y = Edge[i], z = Leng[i];
        if (d[y] != d[x] + 1 || !z) continue;
        int k = dinic(y, min(rest, z));
        if (!k) d[y] = 0;
        else {
            Leng[i] -= k;
            Leng[i^1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int main() {
    cin >> n;
    s = n + 1, t = n + 2, S = n + 3, T = n + 4;
    for (int i = 1; i <= n; i++) {
        ins(s, i, 0, inf);
        ins(i, t, 0, inf);
        int k;
        scanf("%d", &k);
        while (k--) {
            int x;
            scanf("%d", &x);
            ins(i, x, 1, inf);
        }
    }
    for (int i = 1; i <= t; i++) {
        if (d[i] > 0) add(S, i, d[i]);
        else if (d[i] < 0) add(i, T, -d[i]);
    }
    while (bfs()) while (dinic(S, inf));
    ins(t, s, 0, inf);
    while (bfs()) while (dinic(S, inf));
    cout << Leng[tot] << endl;
    return 0;
}