网络流之最大流与二分匹配（二）

网络流算法遍历图的时候，一般必须沿着容量 $\textbf{edges}(i) > 0$ 的边走

Dinic 算法

Acwing2172

• $\bold{dinic}(u, \ limit)$ 算法沿分层图推进
• 推进过程要求增广路存在，也就是检查的边 $c_f(i) > 0$ 容量必须大于 $0$

const int maxn = 10000 + 10, maxm = 200000 + 10;
const int inf = 0x3f3f3f3f;
int n, m, S, T;
int head[maxn], edges[maxm], ver[maxm], ne[maxm], tot = 1;

void add(int a, int b, int c) {
    ver[++tot] = b; edges[tot] = c; ne[tot] = head[a]; head[a] = tot;
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && edges[i]) {
                cur[y] = head[y];
                d[y] = d[x] + 1;
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dfs(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; i && limit > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && edges[i]) {
            int t = dfs(v, min(edges[i], limit-flow));
            if (!t) d[v] = -1;
            edges[i] -= t, edges[i^1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) {
        while (true) {
            flow = dfs(S, inf);
            if (flow == 0) break;
            res += flow;
        }
    }
    return res;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d", &n, &m, &S, &T);
    while (m--) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        add(u, v, c);
        add(v, u, 0);
    }

    // dinic
    int ans = dinic();
    printf("%d\n", ans);
}

三个优化

• 流量剪枝 $limit > flow$
• 当前弧优化
• 废点优化 $\textbf{if} \ t = 0: d(v) = -1$

其他细节
每一次用 $\textbf{bfs}$ 构造分层图的时候
要记得初始化当前弧 $\text{cur}$，对每个点 $x$，令 $\text{cur}(x) \leftarrow \text{head}(x)$

最大二分匹配问题

问题描述

给定一个无向图 $G = (V, E)$，一个匹配是边的一个子集 $M \subseteq E$
使得对于所有节点 $\forall v \in V$，子集 $M$ 中最多有一条边与 $v$ 相连

对于节点 $v$，在子集 $M$ 中有边与 $v$ 相连，则称节点 $v$ 是由 $M$ 所匹配
否则，节点 $v$ 是没有匹配的
最大匹配 $M$，即对于任意匹配 $M'$，均有 $|M| \geqslant |M'|$

寻找最大二分匹配

初步分析如下

• 每个节点至少有一条相连的边，所以 $|E| \geqslant |V|/2$
• $|E| \leqslant |E'| = |E| + |V| \leqslant 3|E|$

所以 $|E'| = \Theta (E)$

引理
设 $G = (V, E)$ 是一个二分图，其节点划分是 $V = L \cup R$，不妨设 $G' = (V', E')$
是图 $G$ 对应的流网络。如果 $M$ 是 $G$ 中的一个匹配，则在流网络 $G'$ 中存在一个整数值的流 $f$
使得 $|f| = |M|$。相反，如果 $f$ 是 $G'$ 中的一个整数值的流，同样在 $G$ 中存在一个匹配 $M$，
使得 $|M|=|f|$

• 已知图 $G$ 的一个匹配 $M$，可以定义流 $f$ 如下
  • 如果边 $(u, v) \in M \Longrightarrow f(s, u) = f(u, v) = f(v, t) = 1$
    而其他属于 $E'$ 的边 $(u, v)$，定义 $f(u, v) = 0$
  • 另一方面，对于任意节点 $\forall \ v$，因为 $M$ 最多只有一条边与 $v$ 相连，
    所以子集 $M$ 中的边所诱导的路径 $s \to u \to v \to t$ 是节点不相交的
    横跨切割 $\{L \cup \{s\} , R \cup \{t\}\}$ 的净流量等于 $M$，$|M| = |f|$
• 设 $f$ 为 $G'$ 中的一个整数值的流，并且设

  $$M = \{(u, v): u \in L, v \in R, \text{并且 } f(u, v) > 0\}$$

  • 每个节点 $u \in L$ 仅有一条进入的边 $(s, u)$，容量为 $1$，也就是说最多有 $1$ 单位流量流入
  • 根据流量守恒，离开节点的流也必须有 $1$ 个单位的流量，因为 $|f|$ 为整数，
    所以 $1$ 单位的流量只能最多从 $1$ 条边流出
    存在 $v \in R$，使得 $f(u, v) = 1$，并且 $u$ 的出边中仅有 $1$ 条带有正的权值
    由此，集合 $M$ 是一个匹配
  • $\forall u \in L, f(s, u) = 1$，并且 $(u, v) \in E-M$，$f(u, v) = 0$
    横跨切割 $(L \cup \{s\}, R \cup \{t\})$ 的净流量 $f(L \cup \{s\}, R \cup \{t\}) = |M|$
    由此 $|M|=|f|$

推论
二分图 $G$ 中的一个最大匹配 $M$ 的基数等于其对应的流网络 $G'$ 中的某一最大流 $|f|$ 的值

如果 $M$ 是最大匹配，但 $|f|$ 不是最大流，那么存在一个最大流 $|f'| > |f|$
而根据引理，此时 $f'$ 对应原来二分图的一个匹配 $M'$，其基数为
$|M'| = |f'| > |f| = |M|$ 这与 $M$ 是一个最大匹配矛盾

同样，如果 $f$ 是 $G'$ 中的一个最大流，其对应的匹配是 $G$ 的一个最大匹配

Acwing2175

• 方案输出，可以遍历所有的正向边
• 如果发现边的容量为 $0$，那么说明这个边被用到了，构成了一组方案

const int maxn = 100 + 10, maxm = 6000 + 10;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], ne[maxm], tot = 1;
int n, m, S, T;

void add(int a, int b, int c) {
    ver[++tot] = b; e[tot] = c; ne[tot] = head[a]; head[a] = tot;
    ver[++tot] = a; e[tot] = 0; ne[tot] = head[b]; head[b] = tot;
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i] > 0) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) {
        while (true) {
            flow = dinic(S, inf);
            if (flow == 0) break;
            res += flow;
        }
    }
    return res;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &m, &n);
    S = 0, T = n+1;
    for (int i = 1; i <= m; i++) add(S, i, 1);
    for (int i = m+1; i <= n; i++) add(i, T, 1);
    int a, b;
    while (scanf("%d%d", &a, &b) && a != -1) add(a, b, 1);

    // then solve
    printf("%d\n", dinic());
    for (int i = 2; i <= tot; i += 2) {
        if (ver[i] > m && ver[i] <= n && e[i] == 0) {
            printf("%d %d\n", ver[i^1], ver[i]);
        }
    }
}

二分图的多重匹配

Acwing2179

const int maxn = 430, maxm = (150 * 270 + maxn) * 2;
const int inf = 0x3f3f3f3f;
int tot = 0, n, m, S, T;
int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;

void add(int a, int b, int c) {
    ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
    ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int cur[maxn], d[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i]) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = dinic(S, inf)) res += flow;
    return res;
}

void out() {
    for (int u = 1; u <= m; u++) {
        for (int i = head[u]; i; i = ne[i]) {
            if (ver[i] > m && ver[i] <= n+m && !e[i]) printf("%d ", ver[i]-m);
        }
        printf("\n");
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &m, &n);
    S = 0, T = m+n+1;
    for (int i = 1; i <= m; i++) {
        int r;
        scanf("%d", &r);
        add(S, i, r);
        tot += r;
    }
    for (int i = 1; i <= n; i++) {
        int c;
        scanf("%d", &c);
        add(m+i, T, c);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) add(i, m+j, 1);
    }

    // then dinic
    if (dinic() != tot) {
        printf("0\n");
        return 0;
    }

    printf("1\n");
    out();
}

无源汇上下界可行流

Acwing2188

const int maxn = 200 + 10, maxm = (10210 + maxn) * 2;
const int inf = 0x3f3f3f3f;

int head[maxn], ver[maxm], e[maxm], ne[maxm], L[maxm], idx = 1, tot = 0;
int n, m, S, T, delta[maxn];
void add(int a, int b, int c, int d) {
    ver[++idx] = b; e[idx] = d-c; L[idx] = c; ne[idx] = head[a]; head[a] = idx;
    ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i]) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = dinic(S, inf)) res += flow;
    return res;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    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);
        delta[a] -= c, delta[b] += c;
    }
    for (int i = 1; i <= n; i++) {
        if (delta[i] > 0) add(S, i, 0, delta[i]), tot += delta[i];
        else if (delta[i] < 0) add(i, T, 0, -delta[i]);
    }
    //debug(tot);

    if (dinic() != tot) {
        puts("NO");
        return 0;
    }
    puts("YES");
    for (int i = 2; i < 2 + m*2; i += 2) {
        printf("%d\n", e[i^1] + L[i]);
    }
}

有源汇上下界最大流

循环流与具有下界的流
$\text{[2020]}\quad \text{Douglas B.West, Introduction to Graph Theroy, Second Edition(图论导引 原书第二版)}$
$\text{chapter 4},\ \textbf{定理4.3.20}$

• 原网络 $G$ 添加从 $t \to s$ 的具有 $+\infty$ 容量的边，此时的网络有个处处守恒的可行流
  称为循环流
• 对于可行循环流 $C$，在所有节点处引入供应量 $\sigma (x_i)$ 和需求量 $\partial (x_i)$，给定流量约束
  $l(e) \leqslant f(e) \leqslant u(e)$，在每一条边上令 $c(e) = u(e) - l(e)$
  $f^{+}(v)$ 表示离开 $v$ 的总流量，$f^{-}(v)$ 表示进入 $v$ 的总流量

  $$\begin{gathered} l^{-}(v) = \sum_{e \in [V(C)-v, v]} l(e) \\ l^{+}(v) = \sum_{e \in [v, V(C)-v]} l(e) \\ b(v) = l^{-}(v) - l^{+}(v) \end{gathered}$$

  $$\cdots \xrightarrow{l^{-}(v)} v \xrightarrow{l^{+}(v)} \cdots$$

• 由于可行循环流流量处处守恒，所以 $\sum b(v) = 0$，一个循环可行流在每个顶点满足
  $f^{+}(v) - f^{-}(v) = 0$，令 $f'(e) = f(e) - l(e)$

  $$\begin{cases} f'^{+}(v) = f^{+}(v) - l^{+}(v) \\ f'^{-}(v) = f^{-}(v) - l^{-}(v) \end{cases}$$

  可以推出

  $$\begin{cases} l'^{-}(v) = f^{-}(v) - f'^{-}(v) \\ l'^{+}(v) = f^{+}(v) - f'^{+}(v) \end{cases} \xrightarrow{f^{+}(v) = f^{-}(v)}$$

  所以有

  $$l^{-}(v) - l^{+}(v) = b(v) = f'^{+}(v) - f'^{-}(v)$$

  也就是说，$f$ 是 $C$ 中的一个可行流当且仅当
  $f'$ 满足流量约束 $0 \leqslant f'(e) \leqslant c(e)$
  并且在每个顶点处满足 $f'^{+}(v) - f'^{-}(v) = b(v)$
• 这样可以将循环流问题转换为一个供应量和需求量的问题，为了满足流量守恒
  • $b(v) \geqslant 0$，那么 $v$ 向网络供应流量 $|b(v)|$
    建立一个超级源点 $S$，令容量 $c(S, v) = |b(v)|$
  • $b(v) < 0$，则 $v$ 对网络有 $|b(v)|$ 的需求量
    建立一个超级汇点 $T$，$c(v, T) = |b(v)|$
• 这样我们构造出了新网络 $G$，并且之前已经证明了
  $C$ 有一个可行循环流 $f$ 当且仅当 $G$ 有一个满流浸润了离开 $S$ 或进入 $T$ 的所有边
  此时我们称 $G$ 保持一个浸润状态

$\textbf{algorithm}$

• 根据上述方法在原网络 $G$ 的基础上，建立超级源点 $S$ 和 超级汇点 $T$，来满足供需关系
• 在原网络 $G$ 的汇点 $t$ 和 源点 $s$ 中，连一条边使得 $c(t, s) = +\infty$
  此时构造出可行循环流网络，新网络记为 $N$
• $\textbf{dinic}(N)$ 判断新网络是否浸润
• 如果浸润，在浸润状态下 $N$ 的一个可行流记为 $f_0$
  那么 $f_0$ 中从 $s \to t$ 的流量 $f_0(s \to t) = e(t \to s)$
  $e(t \to s)$ 表示执行完 $\textbf{dinic}$ 之后，边 $(t, s)$ 的容量
• 去掉循环流的边 $(t, s)$，再次执行 $\textbf{dinic}$ 算法，使得 $s \to t$ 没有增广路
  $f' = \bold{dinic}(s, t)$，表示执行增广能够增加的流量为 $f'$
  则此时 $(f_0 \uparrow f') = f$，$f$ 即为 $s \to t$ 的上下界最大流

下面来证明这个算法的正确性

注意，这里对于浸润流 $f_0$，$f_0(s \to t)$ 的流量是分散的（因为 $s \to t$ 的路径上可能有很多点）
而 $f_0(t \to s)$ 是可以直接求的，因为我们在残量网络上连了一条 $t \to s, \ c(t, s) = +\infty$ 的边
因为 $f_0(s \to t) = f_0(t \to s) = c(s, t)$，所以求出 $f_0$ 之后
只需要在残量网络中找到表示 $\textbf{edge}(s, t)$ 这条边，即表示 $f_0(s \to t)$

Acwing2189

const int maxn = 210, maxm = (10000 + maxn) * 2;
const int inf = 0x3f3f3f3f;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1, tot = 0;
int A[maxn];
int n, m, s, t, S, T;
void add(int a, int b, int c) {
    ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
    ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i]) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = dinic(S, inf)) res += flow;
    return res;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d", &n, &m, &s, &t);
    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, d-c);
        A[a] -= c, A[b] += c;
    }
    for (int i = 1; i <= n; i++) {
        if (A[i] > 0) tot += A[i], add(S, i, A[i]);
        else if(A[i] < 0) add(i, T, -A[i]);
    }
    add(t, s, inf);

    // then solve
    if (dinic() != tot) {
        puts("No Solution");
        return 0;
    }

    int res = e[idx];
    e[idx] = e[idx-1] = 0;
    S = s, T = t;
    int ans = res + dinic();
    printf("%d\n", ans);
}

有源汇上下界最小流

之前已经证明过

$$|f_0| + |f'(s \to t)| = f(s \to t)$$

所以 $f_{\max}(s \to t) = |f_0| + \max \{f'(s \to t)\}$，$f_{\min}(s \to t) = |f_0| + \min \{f'(s \to t)\}$
由于 $f'(s \to t) = -f'(t \to s)$，所以
$\min \{f'(s \to t)\} = - \max \{f'(t \to s)\}$

• 于是我们求出浸润流 $f_0$ 之后，在残量网络中求一遍 $t \to s$ 的最大流
• $\textbf{ans} = f_0 - \textbf{dinic}(t, s)$

多源汇最大流

$\textbf{algorithm}$

• 建立一个超级源点 $S$，对于所有源点 $\textbf{for} \ \forall \ s_i$
  建立一条容量 $\infty$ 的边，即 $c(S, s_i) = \infty$
• 同时对于所有汇点，建立超级汇点 $T$，使得 $c(t_i, T) = \infty$
• 原网络的最大流等于 $f(S, T)$，即 $S \to T$ 的最大流

$\textbf{proof}$

• 对于新图 $G'$ 的一个可行流，它一定是原图的一个可行流，因为除了 $S, T$
  其余的点都满足容量限制和流量守恒
• 对于原图 $G$ 的一个可行流 $f$，对于 $v \in \{V - \{s_i, t_i, S, T\}\}$
  它一定满足容量限制和流量守恒，于此同时，我们可以通过 $f(S, s_i), \ f(t_i, T)$
  来补偿从 $s_i$ 流向网络的流量，使得所有 $s_i, t_i$ 也满足流量守恒
  另外由于 $c(S, s_i) = \infty, \ c(t_i, T) = \infty$，容量限制也一定满足
  所以对于新图 $G'$ 来说，$f$ 诱导的流 $f'$ 也一定是一个可行流

Acwing2234

const int maxn = 10000 + 10, maxm = (100000 + maxn) * 2;
const int inf = 0x3f3f3f3f;
int n, m, sc, tc, S, T;
int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
void add(int a, int b, int c) {
    ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
    ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i]) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = dinic(S, inf)) res += flow;
    return res;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d%d", &n, &m, &sc, &tc);
    S = 0, T = n+1;
    while (sc--) {
        int x;
        scanf("%d", &x);
        add(S, x, inf);
    }
    while (tc--) {
        int x;
        scanf("%d", &x);
        add(x, T, inf);
    }
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", dinic());
}