网络流

网络：一类有向图 \(G=(V,E)\)，\(E\) 中的每条边 \((u, v)\) 都有一个被称为容量的权值，记作 \(w(u, v)\)；当 \((u,v)\notin E\) 时，可以假定 \(w(u,v)=0\)。

源点 \(s\) 和汇点 \(t\)：网络中两个特殊的点。

流：每条边有一个额外的权值 \(f(u,v)\)，称为流。流需要满足一些限制：

容量限制：对于每条边，流经该边的流量不得超过该边的容量，即 \(0\le f(u,v) \leq w(u,v)\)；
流守恒：除 \(s,t\) 两点外，任意结点 \(u\) 的净流量为 \(0\)。

流的流量：\(s\) 的净流量（或 \(t\) 的净流量的相反数）称为流的流量。

\(s\)-\(t\) 割：若两个集合 \(S,T\) 满足 \(S\cup T=V\)，\(S\cap T=\varnothing\)，则称 \(\{S,T\}\) 为网络 \(G\) 的一个 \(s\)-\(t\) 割。

割的容量：\(\sum_{u\in S}\sum_{v\in T}{w(u,v)}\) 称为割 \(\{S,T\}\) 的容量。

最大流 / 最小割

我们主要使用增广路算法求得最大流 / 最小割。不同求最大流的算法的主要差异在于求增广路的算法。

定义残量网络 \(G'=(V,E')\)，其上的边权（容量） \(g(u,v)=w(u,v)-f(u,v)\)。注意：反边在残量网络上也有对应的边，其容量为原边的流量。建出反边是为了方便退流，这本质上是一种反悔贪心，可以避免先前的错误决策导致整体变劣。

定义路径的容量为其上所有边的容量的最小值。我们只考虑容量不为 \(0\) 的路径。（否则没有意义）

残量网络中一条（容量不为 \(0\) 的）从 \(s\) 指向 \(t\) 的路径被称为增广路。

如果存在容量为 \(k\) 的增广路，则我们可以给增广路上的所有边都增加 \(k\) 的容量，使总流量增大 \(k\)，而不影响流的合法性。因此，最大流的残量网络中一定不包含增广路。

最大流最小割定理

对于任意网络图 \(G=(V,E)\)，其最大流 \(|f|\) 和最小割 \(||S,T||\) 大小相等。

该定理能够说明增广路算法求解最大流的正确性。

证明

引理

对于网络 \(G=(V,E)\) 和其上任意一个流 \(f\) 和割 \(\{S,T\}\)，有 \(|f|\le||S,T||\)。

证明

\[ \begin{align*} |f|&=f(S)\\ &=\sum_{u\in S}\sum_{v\in T}\big(f(u,v)-f(v,u)\big)\\ &\le \sum_{u\in S}\sum_{v\in T}f(u,v)\\ &\le \sum_{u\in S}\sum_{v\in T}w(u,v)\\ &= ||S,T|| \end{align*} \]

第一个不等号在所有 \(T\rightarrow S\) 的边均空流时取等；第二个不等号在所有 \(S\rightarrow T\) 的边均空流时取等。

我们现在给出构造，证明存在一个流 \(f\) 和割 \(\{S,T\}\)，使得 \(|f|=||\{S,T\}||\)，显然此时 \(f\) 是最大流，\(||\{S,T\}||\) 是最小割。

考虑对原图不断增广，直到不存在增广路。此时在残量网络 \(G'\) 中，我们将源点 \(s\) 能够（通过容量不为 \(0\) 的边）到达的点组成的点集记为 \(S\)，记 \(T=V/S\)。显然，所有 \(S\rightarrow T\) 的边均满流，所有 \(T\rightarrow S\) 的边均空流；否则从 \(s\) 点出发，可以沿着一条容量不为 \(0\) 的边走到 \(T\) 中的某个点。

这正是引理中的取等条件。这说明流 \(f\) 和割 \(\{S,T\}\) 的容量相等。因此增广算法得到的一定是最大流。

Dinic 算法

Dinic 算法通过一次 bfs 得到所有点到源点 \(s\) 的距离，从而限制 dfs 只走最短的增广路。其时间复杂度为 \(O(n^2m)\)，在简单情况下跑不满。由于其时间复杂度证明过于复杂，请参考 OI-Wiki。

namespace dinic {
    int que[N], hd, tl;
    int dep[N], now[N];

    // bfs 初始化距离数组（dep）
    bool bfs() {
        for(int i = 1; i <= t; i++) dep[i] = 0;
        for(int i = 1; i <= t; i++) now[i] = head[i];
        hd = 1, tl = 0;
        dep[s] = 1;
        que[++tl] = s;
        while(hd <= tl) {
            int u = que[hd++];
            if(u == t) return true; // 找到了一条合法路径，则其它路径都不是到达 t 的最短路，直接返回 true。
            for(int i = head[u]; i; i = pool[i].next) {
                int v = pool[i].v, w = pool[i].w;
                if(dep[v] || !w) continue;
                dep[v] = dep[u] + 1;
                que[++tl] = v;
            }
        }
        return false; // 若没有增广路，则返回 false
    }

    // 找增广路
    // sum 表示 u 前面的节点本次可以提供最多 sum 的流量
    int dfs(int u, int sum) {
        if(u == t) return sum;
        int flow = 0;
        for(int i = now[u]; i && sum; i = pool[i].next) {
            now[u] = i;
            int v = pool[i].v, w = pool[i].w;
            // 只走最短路
            if(dep[v] != dep[u] + 1 || !w) continue;
            int k = dfs(v, min(sum, w));
            if(!k) {
                // 剪掉满流的儿子
                dep[v] = 0;
            } else {
                // 更新容量
                pool[i].w -= k;
                pool[i ^ 1].w += k;
                flow += k;
                sum -= k;
            }
        }
        return flow;
    }

    // 计算最大流
    int calc() {
        int flow = 0;
        while(bfs()) flow += dfs(s, INF);
        return flow;
    }
}

网络流建模

许多非图论问题都可以通过建模转换成网络上的最大流 / 最小割问题。其建模方式因题而异，需要具体分析。

注意短路

建图时通常会使用到 \(+\infty\) 容量的边。如果 \(s\rightarrow t\) 之间存在容量为 \(+\infty\) 的路径，则会导致短路，使得最大流结果无效。因此需要特别注意输入数据是否会使建出的图短路。

技巧

我们希望构造出一个网络 \(G\)，使得每种合法方案都一一对应 \(G\) 的一个 \(s\)-\(t\) 割，并且方案的代价等于割的容量。

这样，我们只需要求出 \(G\) 的最小割就是原问题的最优解。

P2774 方格取数问题

题意

有一个 \(n\) 行 \(m\) 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。

我们将两个互斥的格子用一条边相连，会形成一个二分图。因此原问题等价于二分图最大权独立集。考虑使用网络流求解。

设二分图左侧的点集为 \(A\)，右侧点集为 \(B\)。我们将所有无向边都替换为 \(A\rightarrow B\) 的有向边，容量为 \(+\infty\)。然后从源点 \(s\) 向 \(A\) 中的每一个节点 \(u\) 连接一条边，容量为 \(w_u\)；从 \(B\) 中的每一个节点 \(v\) 向汇点 \(t\) 连接一条边，容量为 \(w_v\)。

最优性分析

将价值转换为代价：记一种方案的代价为：所有没有被选择的节点的权值和。显然，最终的价值等于总价值减去代价。因此我们只需要最小化代价即可。

我们现在证明：选点方案一一对应网络图的所有 \(s\)-\(t\) 割，并且选点方案的代价等于割的容量。当且仅当一个节点 \(u\in A\) 且存在一条 \(s\rightarrow u\) 的合法路径（容量 \(>0\)），或节点 \(u\in B\) 且存在一条 \(u\rightarrow t\) 的合法路径，该节点在原图上为选中状态。

显然，如果两个节点在原图上有边相连，则它们不可能同时选中（中间边权为 \(+\infty\)，不可能被割），这保证了方案的合法性。如果 \(A\) 中的一个节点 \(u\) 与 \(t\) 相连，则 \(s\rightarrow u\) 的边一定被割掉了，产生了对应的代价。因此割的容量与方案的代价相等，保证了最优性。

因此，这样建模一定能得到一个合法且最优的方案。

代码

#include<iostream>
#define ll long long
using namespace std;
const int N = 105 * 105;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v;
    ll w;
    int next;
} pool[2 * 4 * N];
int ne = 1, head[N], now[N];

void addEdge(int u, int v, ll w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, m, s, t;
int a[N];

int dep[N];
int que[N], hd, tail;

bool bfs() {
    for(int i = 1; i <= t; i++) dep[i] = 0;
    for(int i = 1; i <= t; i++) now[i] = head[i];
    dep[s] = 1;
    hd = 1, tail = 0;
    que[++tail] = s;
    while(hd <= tail) {
        int u = que[hd++];
        for(int i = head[u]; i; i = pool[i].next) {
            int v = pool[i].v;
            ll w = pool[i].w;
            if(w && !dep[v]) {
                dep[v] = dep[u] + 1;
                que[++tail] = v;
                if(v == t) return true;
            }
        }
    }
    return false;
}

ll dfs(int u, ll sum) {
    if(u == t) return sum;
    ll flow = 0;
    for(int i = now[u]; i && sum; i = pool[i].next) {
        now[u] = i;
        int v = pool[i].v;
        ll w = pool[i].w;
        if(!w || dep[v] != dep[u] + 1) continue;
        ll k = dfs(v, min(sum, w));
        if(!k) dep[v] = 0;
        else {
            pool[i].w -= k;
            pool[i ^ 1].w += k;
            sum -= k;
            flow += k;
        }
    }
    return flow;
}

ll sum;

signed main() {

    cin >> n >> m;
    s = n * m + m + 1;
    t = s + 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i * m + j];
            sum += a[i * m + j];
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if((i + j) & 1) {
                addEdge(s, i * m + j, a[i * m + j]);
                addEdge(i * m + j, s, 0);
                for(int k = 0; k < 4; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(1 <= x && x <= n && 1 <= y && y <= m) {
                        addEdge(i * m + j, x * m + y, (int)INF);
                        addEdge(x * m + y, i * m + j, 0);
                    }
                }
            } else {
                addEdge(i * m + j, t, a[i * m + j]);
                addEdge(t, i * m + j, 0);
            }
        }
    }

    ll ans = 0;
    while(bfs()) ans += dfs(s, INF);

    cout << (sum - ans) << endl;

    return 0;
}

P4313 文理分科

题意

给定一个带权网格图，你需要将网格图上的每个格子染成黑白两种颜色。将点 \((i,j)\) 染成黑色会产生 \(a_{i,j}\) 的价值，染成白色产生 \(b_{i,j}\) 的价值。若一个点 \((i,j)\) 和相邻的点都为黑色，则额外产生 \(sa_{i,j}\) 价值；若都为白色，则额外产生 \(sb_{i,j}\) 的价值。

技巧

若题目表述为：“若满足一些条件，则产生额外的代价或价值”，可以考虑使用网络流最小割求解。

网络流