「v3」F - 图论

    「v3」F - 图论

    F - 图论 杂项

    图论基础

    参考:

    图的储存

    邻接表的封装:

    template <const int N, const int M>
    struct adj {
        int tot, head[N], ver[M], edge[M], Next[M];
        void add_edge(int u, int v, int w) {
            ver[++ tot] = v;    edge[tot] = w;    Next[tot] = head[u];    head[u] = tot;
        } 
    };

    邻接表的储存成对变换:在具有双向边的图中,把正反方向的边分别储存在邻接表的位置 n,n+1n, n + 1(nn 为偶数),就可以通过 xor 1\mathrm{xor} \ 1 的操作获得当前边的反向边的储存位置。具体实现时,初始化要令 tot = 1。

    图的遍历

    BFS

    • Breadth First Search。

    DFS

    • Depth First Search。

    拓扑排序

    拓扑序:一张有向无环图中的一个节点序列 AA,满足对于图中的每条边 (x,y)(x, y),xx 在 AA 中都出现在 yy 之前。

    • 维护一个入度为 00 的点集 SS。每次扩展时,从 SS 中取出任意一点 uu 加入拓扑序,然后枚举 uu 的所有出边,若某个出点 vv 在删除了 (u,v)(u, v) 这条边之后入度变为 00,则将 vv 加入点集 SS。
    • 由拓扑排序的算法得到的拓扑序按照层次分层,但同一层次的节点未必需要在拓扑序中相邻。
    • 若要求字典序最小的拓扑序,将队列换成优先队列即可。
    int tot, head[N], ver[M], Next[M], deg[N];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;    deg[v] ++;
    }
    
    int seqlen, seq[N];
    
    void topsort() {
        std::queue<int> q;
    
        for (int i = 1; i <= n; i ++)
            if (deg[i] == 0) q.push(i);
    
        while (q.size()) {
            int u = q.front(); q.pop();
    
            seq[++ seqlen] = u;
    
            for (int i = head[u]; i; i = Next[i]) {
                int v = ver[i];
                if (-- deg[v] == 0) q.push(v);
            }
        }
    }

    欧拉路、欧拉回路

    欧拉路:恰好不重不漏的经过每条边一次(可以重复经过图中的节点)的通路。

    欧拉回路:恰好不重不漏的经过每条边一次(可以重复经过图中的节点)的回路。

    欧拉图:存在欧拉回路的无向图。

    欧拉图的判定:

    • 一张无向图为欧拉图,当且仅当无向图连通,并且每个点的度数都是偶数。
    • 一张有向图为欧拉图,当且仅当非零度点强联通,每个点的入度与出度相等。

    欧拉路的存在性判定:一张图中存在欧拉路,当且仅当无向图连通,并且途中恰好有两个节点的度数为奇数,其他节点的度数都是偶数。这两个度数为奇数的节点就是欧拉路的起点 SS 和终点 TT。

    三元环计数、四元环计数

    无向图三元环计数:

    • 将所有点以度数为第一关键字(小到大)编号为第二关键字(小到大)排序,将所有边按排名从小到大定向,形成一张 DAG。
    • 此时所有三元环的边向情况,只有 x→yx \to y、y→zy \to z、x→zx \to z 这一种情况。
    • 枚举点 xx,第一轮枚举 xx 在新图中的出边,将所到达的点 zz 打上标记;第二轮枚举 xx 在新图中的出边,对于所到达的点 yy,再枚举 yy 在新图中的出边到达的点 zz,如果 zz 上有标记,则 x,y,zx, y, z 构成三元环。
    std::vector<int> e[N];
    
    int id[N], rk[N];
    std::vector<int> out[N];
    
    bool vis[N];
    
    int main() {
        for (int i = 1, u, v; i <= m; i ++)
            e[u].push_back(v), e[v].push_back(u);
    
        for (int i = 1; i <= n; i ++) id[i] = i;
        std::sort(id + 1, id + 1 + n);
    
        for (int i = 1; i <= n; i ++) rk[id[i]] = i;
    
        for (int u = 1; u <= n; u ++)
            for (int v : e[u]) if (rk[u] < rk[v]) out[u].push_back(v);
    
        int ans = 0;
        for (int x = 1; x <= n; x ++) {
            for (int z : out[x]) vis[z] = 1;
    
            for (int y : out[x])
                for (int z : out[y])
                    if (vis[z]) ans ++;
    
            for (int z : out[x]) vis[z] = 0;
        }
    }

    无向图三元环计数,时间复杂度:O(mm)\mathcal{O}(m\sqrt{m})。

    无向图三元环计数,时间复杂度分析:

    • 记 degu\mathrm{deg}_u 为原图中点 uu 的度,outu\mathrm{out}_u 为新图中点 uu 的出度。可证 outu\mathrm{out}_u 为 O(m)\mathcal{O}(\sqrt{m}) 级别。
      • 若 degu≤m\mathrm{deg}_u \leq \sqrt{m},则 outu≤m\mathrm{out}_u \leq \sqrt{m}。
      • 若 degu>m\mathrm{deg}_u > \sqrt{m},则 uu 在新图中指向的点的度数大于 m\sqrt{m},故 outu≤m\mathrm{out}_u \leq \sqrt{m}。
    • 上述流程的复杂度,相当于对定向后每条边 (u,v)(u, v) 的 vv 的 outv\mathrm{out}_v 求和。每条边的贡献为 O(m)\mathcal{O}(\sqrt{m}) 级别,故上述流程的复杂度为 O(mm)\mathcal{O}(m\sqrt{m})。

    无向图三元环计数的推论:无向图的三元环个数为 O(mm)\mathcal{O}(m\sqrt{m}) 级别。

    有向图三元环计数:转化为无向图三元环计数,找到三元环时判断方向即可。

    竞赛图三元环计数:记点 ii 的出度为 outi\mathrm{out}_i,则三元环个数为

    (n3)−∑i=1n(outi2)\dbinom{n}{3} - \sum\limits_{i = 1}^n \dbinom{\mathrm{out}_i}{2}

    无向图四元环计数:

    • 将所有点以度数为第一关键字(小到大)编号为第二关键字(小到大)排序,将所有边按排名从小到大定向,形成一张 DAG。
    • 此时所有四元环的边向情况,只有两条形如 (x,y)(x, y)、y→zy \to z 的路径拼起来的情况:
      • x→y1x \to y_1、y1→zy_1 \to z、x→y2x \to y_2、y2→zy_2 \to z。
      • x←y1x \gets y_1、y1→zy_1 \to z、x→y2x \to y_2、y2→zy_2 \to z。
      • x←y1x \gets y_1、y1→zy_1 \to z、x←y2x \gets y_2、y2→zy_2 \to z。
    • 枚举点 xx,再枚举 xx 在原图中的出边,对于所到达的点 yy,再枚举 yy 在新图中的出边到达的点 zz(为避免第三种边向情况重复计数,此处枚举到的 zz 应满足 rkx<rkz\mathrm{rk}_x < \mathrm{rk}_z),则先前枚举的所有形如 (x,y)(x, y)、y→zy \to z 的路径都与当前枚举的路径构成四元环。
    std::vector<int> e[N];
    
    int id[N], rk[N];
    std::vector<int> out[N];
    
    int cnt[N];
    
    int main() {
        for (int i = 1, u, v; i <= m; i ++)
            e[u].push_back(v), e[v].push_back(u);
    
        for (int i = 1; i <= n; i ++) id[i] = i;
        std::sort(id + 1, id + 1 + n);
    
        for (int i = 1; i <= n; i ++) rk[id[i]] = i;
    
        for (int u = 1; u <= n; u ++)
            for (int v : e[u]) if (rk[u] < rk[v]) out[u].push_back(v);
    
        int ans = 0;
        for (int x = 1; x <= n; x ++) {
            for (int y : e[x])
                for (int z : out[y])
                    if (rk[x] < rk[z]) ans += cnt[z] ++;
    
            for (int y : e[x])
                for (int z : out[y])
                    if (rk[x] < rk[z]) cnt[z] = 0;
        }
    }

    无向图四元环计数,时间复杂度:O(mm)\mathcal{O}(m\sqrt{m})。

    无向图四元环计数,时间复杂度分析:同无向图三元环计数。

    Prufer 序列

    Prufer 序列:一个包含 n−2n-2 个取值范围在 [1,n][1, n] 中的正整数的序列。可以理解为带标号的完全图生成树与数列的双射。

    Prufer 序列构造:每次选择一个编号最小的叶结点并删掉它,并且在序列中记录下它连接到的那个结点。重复 n−2n-2 次后,只剩下两个节点后停止。

    Prufer 序列性质:

    • 在构造完 Prufer 序列后原树中会剩下两个结点,其中一个一定是编号最大的点 nn。
    • 每个节点在 Prufer 序列中的出现次数是其度数减 11,叶节点不出现。

    树转 Prufer 序列:

    • O(nlog⁡n)\mathcal{O}(n \log n) 构造:堆优化。
    • O(n)\mathcal{O}(n) 构造:注意到叶节点个数是单点不增的。考虑维护一个指针 pp,初始时 pp 指向编号最小的叶节点。同时维护每个节点的度数,考虑重复如下过程:
      1. 删除节点 pp,并检查是否产生新的叶节点。
      2. 如果产生新的叶节点 xx,比较 x,px, p 的大小关系,若 x>px > p,则不做其他操作;若 x<px < p,则立刻删除 xx,然后检查是否产生新的叶节点 …(重复步骤 2),直到未产生新节点或新节点的编号 >p>p。
      3. 让 pp 自增,直到遇到一个未被删除的叶节点为止。
    int tot, head[N], ver[N * 2], Next[N * 2], deg[N];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;    deg[v] ++;
    }
    
    int Fa[N];
    
    void dfs(int u) {
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (Fa[v]) continue;
            Fa[v] = u;
            dfs(v);
        }
    }
    
    int prufer[N];
    
    int main() {
        Fa[n] = -1, dfs(n);
    
        int leaf = 0, p = 0;
        for (int i = 1; i <= n; i ++)
            if (deg[i] == 1) { leaf = p = i; break; }
        for (int i = 1; i <= n - 2; i ++) {
            int x = Fa[leaf];
    
            prufer[i] = x;
    
            if (-- deg[x] == 1 && x < p) {
                leaf = x;
            } else {
                p ++;
                while (deg[p] != 1) p ++;
                leaf = p;
            }
        }
    
        for (int i = 1; i <= n - 2; i ++)
            printf("%d ", prufer[i]);
        puts("");
    }

    Prufer 序列转树:通过 Prufer 序列反推每个节点的度数。依次枚举 Prufer 序列的每一个点,每次选择一个度数为 11 且编号最小的节点,与当前枚举到的 Prufer 序列的点连边,并且令这两个点的度数减 11。重复 n−2n-2 次后,只剩下两个度数为 11 的节点,将这两个点连边。

    • O(nlog⁡n)\mathcal{O}(n \log n) 构造:堆优化。
    • O(n)\mathcal{O}(n) 构造:同 “树转 Prufer 序列”。
    int n;
    int prufer[N];
    
    int deg[N]; 
    
    std::pair<int, int> e[N];
    
    int main() {
        for (int i = 1; i <= n; i ++) deg[i] = 1;
        for (int i = 1; i <= n - 2; i ++) deg[prufer[i]] ++;
    
        int leaf = 0, p = 0;
        for (int i = 1; i <= n; i ++)
            if (deg[i] == 1) { leaf = p = i; break; }
        for (int i = 1; i <= n - 2; i ++) {
            int x = prufer[i];
    
            e[i] = std::make_pair(leaf, x);
    
            if (-- deg[x] == 1 && x < p) {
                leaf = x;
            } else {
                p ++;
                while (deg[p] != 1) p ++;
                leaf = p;
            }
        }
    
        e[n - 1] = std::make_pair(leaf, n);
    }

    Cayley 公式(有标号完全图生成树计数):有标号完全图有 nn−2n^{n-2} 棵生成树。

    F - 图论 最小生成树

    Kruskal

    • O(n+mlog⁡m)\mathcal{O}(n + m \log m)。
    struct edg {
        int u, v, w;
        bool operator < (const edg &rhs) const {
            return w < rhs.w;
        }
    } e[M];
    
    int fa[N];
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    
    void kruskal() {
        std::sort(e + 1, e + 1 + m);
     
        for (int i = 1; i <= n; i ++) fa[i] = i;
        for (int i = 1; i <= m; i ++) {
            int u = e[i].u, v = e[i].v, w = e[i].w;
            int p = get(u), q = get(v);
    
            if (p == q) continue;
    
            // Calculate the information of the (u, v, w)
    
            fa[p] = q;
        }
    } 

    Kruskal 重构树

    Kruskal 重构树:按 Kruskal 的流程,每加入一条边 (u,v,w)(u, v, w),就新建一个点 xx,同时将 xx 的点权设为 ww,将 u,vu, v 所在的树的根节点分别设为点 xx 的左儿子与右儿子。在进行 n−1n - 1 轮合并后,得到了一棵恰有 nn 个叶子的二叉树,同时每个非叶子节点恰好有两个儿子,这棵树即为 kruskal 重构树。

    struct edg {
        int u, v, w;
        bool operator < (const edg &rhs) const {
            return w < rhs.w;
        }
    } e[M];
    
    namespace KRT {
        const int SIZE = N * 2;
    
        int nClock;
        struct node {
            int lc, rc;
            int val;
        } t[SIZE];
    
        int fa[SIZE];
        int get(int x) {
            return fa[x] == x ? x : fa[x] = get(fa[x]);
        }
    
        void build() {
            std::sort(e + 1, e + 1 + m);
    
            nClock = n;
            for (int i = 1; i <= n; i ++) fa[i] = i;
            for (int i = 1; i <= m; i ++) {
                int u = e[i].u, v = e[i].v, w = e[i].w;
                int p = get(u), q = get(v);
    
                if (p == q) continue;
    
                int x = ++ nClock;
                t[x].val = w, t[x].lc = p, t[x].rc = q;
    
                fa[p] = fa[q] = fa[x] = x;
            }
        }
    }

    Kruskal 重构树的简单性质:

    • kruskal 最小重构树是大根堆,kruskal 最大重构树是小根堆。
    • kruskal 最小重构树中,两叶子节点之间 LCA 的权值,对应原图中两点之间所有简单路径上最大边权的最小值。
    • kruskal 最小重构树中,对于叶子节点 xx 到根的路径上权值 ≤val\leq \mathrm{val} 的最浅节点,其子树内的所有节点,即为从 xx 开始只经过边权 ≤val\leq \mathrm{val} 的边所能到达的节点(满足两点之间所有简单路径上最大边权的最小值 ≤val\leq \mathrm{val})。

    Prim

    • O(n2)\mathcal{O}(n^2)。
    const int inf = 0x3f3f3f3f;
    
    int a[N][N];
    
    int d[N];
    bool exist[N];
    
    void prim() {
        for (int i = 1; i <= n; i ++) d[i] = inf;
        d[1] = 0;
    
        for (int i = 1; i <= n; i ++) exist[i] = 0;
    
        for (int i = 1; i <= n; i ++) {
            int u = 0;
            for (int x = 1; x <= n; x ++)
                if (!exist[x] && (u == 0 || d[x] < d[u])) u = x;
    
            exist[u] = 1;
    
            for (int v = 1; v <= n; v ++)
                if (!exist[v]) d[v] = std::min(d[v], a[u][v]); 
        }
    }

    Brouvka

    • 初始时,每一个点都是一个连通块。每一轮,遍历所有点和边,连接一个连通块中和其他连通块相连的最小边。
    • O((n+m)log⁡n)\mathcal{O}((n + m) \log n)。
    const int inf = 0x3f3f3f3f;
    
    struct edg {
        int u, v, w;
    } e[M];
    
    int fa[N];
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    
    int great_val[N], great_id[N];
    
    void boruvka() {
        for (int i = 1; i <= n; i ++) fa[i] = i;
    
        while (1) {
            for (int i = 1; i <= n; i ++) great_val[i] = inf, great_id[i] = 0;
    
            bool exist = 0;
            for (int i = 1; i <= m; i ++) {
                int p = get(e[i].u), q = get(e[i].v);
                if (p == q) continue;
                exist = 1;
                if (e[i].w < great_val[p]) great_val[p] = e[i].w, great_id[p] = i;
                if (e[i].w < great_val[q]) great_val[q] = e[i].w, great_id[q] = i;
            }
    
            if (!exist) break;
    
            for (int i = 1; i <= n; i ++) {
                if (great_id[i] == 0) continue;
                int id = great_id[i], p = get(e[id].u), q = get(e[id].v);
                if (p == q) continue;
                // Calculate the data of this edge.
                fa[p] = q;
            }
        }
    }
    const int inf = 0x3f3f3f3f;
    
    int cur_block;
    
    int fa[N];
    int get(int x) {
        return fa[x] == x ? x : fa[x] = get(fa[x]);
    }
    
    int great_val[N], great_id[N];
    
    void boruvka() {
        cur_block = n;
        for (int i = 1; i <= n; i ++) fa[i] = i;
    
        while (cur_block ^ 1) {
            for (int i = 1; i <= n; i ++) great_val[i] = inf, great_id[i] = 0;
    
            for (int i = 1; i <= n; i ++) {
                int p = get(i);
                // update the data of this connected block p with i.
            }
    
            for (int i = 1; i <= n; i ++) {
                if (great_id[i] == 0) continue;
                int p = get(i), q = get(great_id[i]);
                if (p == q) continue;
                // Calculate the data of this edge.
                fa[p] = q, cur_block --;
            }
        }
    }

    F - 图论 最短路径

    Dijkstra

    • Dijkstra:O(n2)\mathcal{O}(n^2)。
    • Dijkstra + Heap:O((n+m)log⁡m)\mathcal{O}((n + m) \log m)。
    const int inf = 0x3f3f3f3f;
    
    int tot, head[N], ver[M], edge[M], Next[M];
    void add_edge(int u, int v, int w) {
        ver[++ tot] = v;    edge[tot] = w;    Next[tot] = head[u];    head[u] = tot; 
    }
    
    int dist[N];
    bool vis[N];
    
    void dijkstra() {
        for (int i = 1; i <= n; i ++) dist[i] = inf;
        for (int i = 1; i <= n; i ++) vis[i] = 0;
    
        std::priority_queue< pair<int, int> > q;
        q.push(make_pair(0, 1)), dist[1] = 0;
    
        while (q.size()) {
            int u = q.top().second; q.pop();
    
            if (vis[u]) continue;
            vis[u] = 1;
    
            for (int i = head[u]; i; i = Next[i]) {
                int v = ver[i], w = edge[i];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    q.push(make_pair(-dist[v], v));
                }
            }
        }
    }

    Bellman-ford & SPFA

    • SPFA:O(nm)\mathcal{O}(nm)。
    const int inf = 0x3f3f3f3f;
    
    int tot, head[N], ver[M], edge[M], Next[M];
    void add_edge(int u, int v, int w) {
        ver[++ tot] = v;    edge[tot] = w;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dist[N];
    bool vis[N];
    
    void SPFA() {
        for (int i = 1; i <= n; i ++) dist[i] = inf;
        for (int i = 1; i <= n; i ++) vis[i] = 0;
    
        std::queue<int> q;
        q.push(1), dist[1] = 0;
    
        while (q.size()) {
            int u = q.front(); q.pop(); vis[u] = 0;
    
            for (int i = head[u]; i; i = Next[i]) {
                int v = ver[i], w = edge[i];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (!vis[v]) q.push(v), vis[v] = 1;
                }
            }
        }
    }

    Bellman-Ford 判负环:若经过 nn 轮迭代后,图中仍有能更新的边,则图中有负环。

    SPFA 判负环:设 cntx\mathrm{cnt}_x 表示 11 到 xx 的最短路包含的边数。在迭代的过程中,若发现 cnty≥n\mathrm{cnt}_y \geq n,则图中有负环。

    Floyd

    • Floyd:O(n3)\mathcal{O}(n^3)。
    • Floyd 本质上是 dp。定义 f(k,i,j)f(k, i, j) 表示允许经过 11 到 kk 号点作为中间点(除了 i,ji, j 分别为起点终点,经过的其他点只能是 1∼k1 \sim k 的点)的情况下,点 ii 到点 jj 的最短路。通过滚动数组优化掉了阶段维,才得到最常见的 Floyd 写法。如果以任意的顺序枚举 kk,得到的 f(i,j)f(i, j) 即为允许经过枚举过的点作为中间点的情况下,点 ii 到点 jj 的最短路。

    差分约束

    差分约束:一种特殊的 nn 元一次不等式组,包含 nn 个变量 x1,x2,⋯ ,xnx_1, x_2, \cdots, x_n 以及 mm 组限制关系 xi−xj≤ckx_i - x_j \leq c_k。

    • xi−xj≤ckx_i - x_j \leq c_k 可以变形为 xi≤xj+ckx_i \leq x_j + c_k,形似三角形不等式,因此从点 jj 向点 ii 连一条长度为 ckc_k 的有向边。
    • 若存在负环则无解,否则最短路即为一组合法解。

    同余最短路

    同余最短路,问题 1:给出 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 和一个模数 KK,对于每一个 p∈[0,K)p \in [0, K) 求使得 (∑aixi) mod K=p(\sum a_i x_i) \bmod K = p 的 ∑aixi\sum a_ix_i 最小值。

    • 建 KK 个点,编号为 0∼K−10 \sim K - 1。
    • 对于每一个 p∈[0,K)p \in [0, K) 和每一个 aia_i,令 pp 向 (p+ai) mod K(p + a_i) \bmod K 连一条长度为 aia_i 的边。转化为图论模型。

    同余最短路,问题 2:给出 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n 和一个上界 HH,求 ∑aixi\sum a_ix_i 的数值在 [0,H][0, H] 有多少个解。

    F - 图论 连通性

    无向图 tarjan

    时间戳与追溯值

    时间戳 dfnx\mathrm{dfn}_x:在深度优先遍历的过程中,节点 xx 第一次被访问时的时间顺序。

    追溯值 lowx\mathrm{low}_x:以下节点的时间戳的最小值

    • subtree(x)\mathrm{subtree}(x) 中的节点。
    • 通过一条非搜索树边,能够到达 subtree(x)\mathrm{subtree}(x) 中的节点的点。

    时间戳 dfnx\mathrm{dfn}_x 与追溯值 lowx\mathrm{low}_x 的计算方式:对整张图进行深度优先遍历,一开始 lowx=dfnx\mathrm{low}_x = \mathrm{dfn}_x,考虑从 xx 出发的每条边 (x,y)(x, y)

    • 若 xx 是 yy 的父亲,则
    lowx=min⁡(lowx,lowy)\text{low}_x = \min(\text{low}_x, \text{low}_y)
    • 若 (x,y)(x, y) 为非搜索树边,则
    lowx=min⁡(lowx,dfny)\text{low}_x = \min(\text{low}_x, \text{dfn}_y)

    割点

    割点:满足删去该点以及连接该点的边后,原图不连通的点。

    割点判定法则:在搜索树上,若存在 xx 的某个儿子 yy 满足

    dfnx≤lowy\mathrm{dfn}_x \leq \mathrm{low}_y

    则 xx 为割点。特别地,若 xx 为搜索树的根,则至少要找出两个满足条件的儿子。

    int tot, head[N], ver[M * 2], Next[M * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int root, dfsClock, dfn[N], low[N];
    bool cut[N];
    
    void tarjan(int u) {
        dfn[u] = low[u] = ++ dfsClock;
    
        int cp = 0;
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (!dfn[v]) {
                tarjan(v);
                low[u] = std::min(low[u], low[v]);
                if (dfn[u] <= low[v]) {
                    cp ++;
                    if (u != root || cp > 1) cut[u] = 1;
                }
            } else {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
    
    int main() {
        for (int i = 1; i <= n; i ++)
            if (!dfn[i]) root = i, tarjan(i);
    }

    割边

    割边:满足删去该边后,原图不连通的边。

    割边判定法则:在搜索树上,若 xx 为 yy 的父亲,且满足

    dfnx<lowy\mathrm{dfn}_x < \mathrm{low}_y

    则 (x,y)(x, y) 为割边。

    int tot = 1, head[N], ver[M * 2], Next[M * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int dfsClock, dfn[N], low[N];
    bool bridge[M * 2];
    
    void tarjan(int u, int in_edge) {
        dfn[u] = low[u] = ++ dfsClock;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (!dfn[v]) {
                tarjan(v, i);
                low[u] = std::min(low[u], low[v]);
                if (dfn[u] < low[v]) bridge[i] = bridge[i ^ 1] = 1;
            } else if (i != (in_edge ^ 1)) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
    
    int main() {
        for (int i = 1; i <= n; i ++)
            if (!dfn[i]) tarjan(i, 0);
    }

    点双连通分量

    点双连通:若删去任意一个点(除 u,vu, v 以外),u,vu, v 仍连通,则称 uu 与 vv 是点双连通的。

    点双连通图:不存在割点的无向连通图。

    点双连通分量(v-DCC):无向图的极大点双连通子图。

    v-DCC 的简单性质:

    • 一张无向连通图是 v-DCC,当且仅当任意两个点都包含在至少一个简单环中。
    • 对于一个 v-DCC 的任意两个点,它们之间都有至少两个点不重复的路径。
    • 对于一个 v-DCC 中任意两个点,它们之间简单路径的并集,恰好完全等于这个 v-DCC。
    • 割点至少在两个 v-DCC 中,其他非割点属于且仅属于一个 v-DCC 中。

    v-DCC 的缩点(圆方树):

    • 在圆方树中,原图中每个点对应一个圆点,每个 v-DCC 对应一个方点。
    • 对于每个 v-DCC,令其对应的方点向该 v-DCC 中的每一个圆点连边。每个 v-DCC 构成一个菊花图,多个菊花图通过原图中的割点连接。
    • 对原图做一遍无向图 tarjan。考虑一个 v-DCC 在 DFS 树中的最顶端节点 uu,在点 uu 处确定这个 v-DCC。对于一个树边 (u,v)(u, v),u,vu, v 在同一个 v-DCC 中且 uu 是这个 v-DCC 中的最顶端节点,当且仅当 dfnu=lowv\mathrm{dfn}_u = \mathrm{low}_v。
    • 可以在 DFS 的过程中,维护一个栈,储存还未确定所属 v-DCC(可能有多个)的节点。找到 v-DCC 时,v-DCC 中除了 uu 以外的其他点都集中在栈顶端,只需不断弹出栈顶直到弹出 vv 为止。uu 和被弹出的所有点,构成一个 v-DCC,都需要向新建的方点连边。
    const int SIZE = N * 2;
    
    template <const int N, const int M>
    struct adj {
        int tot, head[N], ver[M], Next[M];
        void add_edge(int u, int v) {
            ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
        }
    };
    
    adj<N, M * 2> G;
    adj<SIZE, SIZE * 2> V;
    
    int dfsClock, dfn[N], low[N];
    int top, stk[N];
    
    int v_dcc;
    
    void tarjan(int u) {
        dfn[u] = low[u] = ++ dfsClock;
        stk[++ top] = u;
    
        for (int i = G.head[u]; i; i = G.Next[i]) {
            int v = G.ver[i];
            if (!dfn[v]) {
                tarjan(v);
                low[u] = std::min(low[u], low[v]);
    
                if (dfn[u] == low[v]) {
                    v_dcc ++;
    
                    int x, p = n + v_dcc;
                    do {
                        x = stk[top --];
                        V.add_edge(x, p), V.add_edge(p, x);
                    } while (x != v);
    
                    V.add_edge(u, p), V.add_edge(p, u);
                }
            } else {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
    
    int main() {
        for (int i = 1, u, v; i <= m; i ++)
            G.add_edge(u, v), G.add_edge(v, u);
    
        for (int i = 1; i <= n; i ++)
            if (!dfn[i]) top = 0, tarjan(i);
    }

    边双连通分量

    边双连通:若删去任意一条边,u,vu, v 仍连通,则称 uu 与 vv 是边双连通的。

    边双连通图:不存在割边的无向连通图。

    边双连通分量(e-DCC):无向图的极大边双连通子图。

    e-DCC 的简单性质:

    • 一张无向连通图是 e-DCC,当且仅当任意一条边都包含在至少一个简单环中。
    • 对于一个 e-DCC 中的任意两个点,它们之间都有至少两个边不重复的路径。
    • 对于一个 e-DCC 中的任意两个点,它们之间简单路径的并集,恰好完全等于这个 e-DCC。
    • 割边不属于任意 e-DCC,其他非割边属于且仅属于一个 e-DCC。
    • 一张图经过 e-DCC 缩点后会得到树或森林。

    e-DCC 的缩点:

    • 对原图做一遍无向图 tarjan。考虑一个 e-DCC 在 DFS 树中的最顶端节点 uu,在点 uu 处确定这个 e-DCC。uu 是这个 e-DCC 中的最顶端节点,当且仅当 dfnu=lowu\mathrm{dfn}_u = \mathrm{low}_u。
    • 可以在 DFS 的过程中,维护一个栈,储存还未确定所属 e-DCC(可能有多个)的节点。找到 e-DCC 时,e-DCC 中的所有点都集中在栈顶端,只需不断弹出栈顶直到弹出 uu 为止。被弹出的所有点,构成一个 e-DCC。
    • 在找出了所有的 e-DCC 后,枚举原图中的所有边 (u,v)(u, v),若 uu 与 vv 不属于同一个 e-DCC,则在 u,vu, v 所属的 e-DCC 之间连一条边。
    template <const int N, const int M>
    struct adj {
        int tot = 1, head[N], ver[M * 2], Next[M * 2];
        void add_edge(int u, int v) {
            ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
        }
    };
    
    adj<N, M * 2> G;
    adj<N, N * 2> V;
    
    int dfsClock, dfn[N], low[N];
    int top, stk[N];
    
    int e_dcc, col[N];
    
    void tarjan(int u, int in_edge) {
        dfn[u] = low[u] = ++ dfsClock;
        stk[++ top] = u;
    
        for (int i = G.head[u]; i; i = G.Next[i]) {
            int v = G.ver[i]; 
            if (!dfn[v]) {
                tarjan(v, i);
                low[u] = std::min(low[u], low[v]); 
            } else if (i != (in_edge ^ 1)) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    
        if (dfn[u] == low[u]) {
            e_dcc ++;
    
            int x;
            do {
                x = stk[top --];
                col[x] = e_dcc;
            } while (x != u);
        }
    }
    
    int main() {
        for (int i = 1, u, v; i <= m; i ++)
            G.add_edge(u, v), G.add_edge(v, u);
    
        for (int i = 1; i <= n; i ++)
            if (!dfn[i]) tarjan(i, 0);
    
        for (int i = 2; i < G.tot; i += 2) {
            int u = G.ver[i ^ 1], v = G.ver[i];
            if (col[u] == col[v]) continue;
    
            V.add_edge(col[u], col[v]), V.add_edge(col[v], col[u]);
        }
    }

    有向图 tarjan

    流图

    时间戳 dfnx\mathrm{dfn}_x:在深度优先遍历的过程中,节点 xx 第一次被访问时的时间顺序。

    流图:给定有向图 G=(V,E)G = (V, E),若存在 r∈Vr \in V,满足从 rr 出发能够到达 VV 中的所有点,则称 GG 是一个流图,其中 rr 称为流图的源点。

    流图中的有向边 (x,y)(x, y) 分类:对于流图中的有向边 (x,y)(x, y),必是以下四种之一

    • 树枝边。指搜索树中的边,即 xx 是 yy 的父节点。
    • 前向边。指搜索树中 xx 是 yy 的祖先节点。
    • 后向边。指搜索树中 yy 是 xx 的祖先节点。
    • 横叉边。指除了以上三种情况之外的边,一定满足 dfnx>dfny\mathrm{dfn}_x > \mathrm{dfn}_y。

    强连通分量

    强连通:若既存在 xx 到 yy 的路径,又存在 yy 到 xx 的路径,则称 xx 与 yy 是强连通的。

    强连通图:任意两点都强连通的有向图。

    强连通分量(SCC):有向图的极大强连通子图。

    时间戳 dfnx\mathrm{dfn}_x:在深度优先遍历的过程中,节点 xx 第一次被访问时的时间顺序。

    追溯值 lowx\mathrm{low}_x:以下节点的时间戳的最小值

    • 栈中的节点。有向图 tarjan 在深度优先遍历的同时维护了一个栈,当访问到节点 xx,保存从 xx 出发的后向边、横叉边形成环的节点:
      • 搜索树上 xx 的祖先节点,记作 anc(x)\mathrm{anc}(x)。
      • 已经访问过,并且存在一条路径到达 anc(x)\mathrm{anc}(x) 的节点。
    • 通过一条从 subtree(x)\mathrm{subtree}(x) 中出发的有向边,以该点为终点。

    时间戳 dfnx\mathrm{dfn}_x 与追溯值 lowx\mathrm{low}_x 的计算方式:对整张图进行深度优先遍历,一开始 lowx=dfnx\mathrm{low}_x = \mathrm{dfn}_x,将 xx 入栈,考虑从 xx 出发的每条边 (x,y)(x, y)

    • 若 yy 没有访问过,则说明 xx 为 yy 的父亲,则
    lowx=min⁡(lowx,lowy)\mathrm{low}_x = \min(\mathrm{low}_x, \mathrm{low}_y)
    • 若 yy 被访问过,且 yy 在栈中,则
    lowx=min⁡(lowx,dfny)\mathrm{low}_x = \min(\mathrm{low}_x, \mathrm{dfn}_y)

    在 xx 回溯之前,若 dfnx=lowx\mathrm{dfn}_x = \mathrm{low}_x,则不断弹出栈顶直到弹出 xx 为止。

    SCC 判定法则:在 xx 回溯之前,若 dfnx=lowx\mathrm{dfn}_x = \mathrm{low}_x,则栈中从 xx 到栈顶的所有节点构成一个 SCC。

    SCC 的缩点:在找出了所有的 SCC 后,枚举原图中的所有边 (u,v)(u, v),若 uu 与 vv 不属于同一个 SCC,则在 u,vu, v 所属的 SCC 之间连一条边。

    template <const int N, const int M>
    struct adj {
        int tot, head[N], ver[M], Next[M];
        void add_edge(int u, int v) {
            ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
        }
    }; 
    
    adj<N, M * 2> G, V;
    
    int dfsClock, dfn[N], low[N];
    int top, stk[N]; bool inc[N];
    
    int scc, col[N];
    std::vector<int> h[N];
    
    void tarjan(int u) {
        dfn[u] = low[u] = ++ dfsClock;
        stk[++ top] = u, inc[u] = 1;
    
        for (int i = G.head[u]; i; i = G.Next[i]) {
            int v = G.ver[i];
            if (!dfn[v]) {
                tarjan(v);
                low[u] = std::min(low[u], low[v]);
            } else if (inc[v]) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    
        if (dfn[u] == low[u]) {
            scc ++;
    
            int x;
            do {
                x = stk[top --], inc[x] = 0;
                col[x] = scc, h[scc].push_back(x);
            } while (x != u);
        }
    }
    
    int main() {
        for (int i = 1, u, v; i <= m; i ++)
            G.add_edge(u, v);
    
        for (int i = 1; i <= n; i ++)
            if (!dfn[i]) tarjan(i);
    
        for (int u = 1; u <= n; u ++)
            for (int i = G.head[u]; i; i = G.Next[i]) {
                int v = G.ver[i];
                if (col[u] == col[v]) continue;
    
                V.add_edge(col[u], col[v]);
            }
    }

    tarjan 编号:tarjan 编号,为原图缩点后 DAG 的拓扑序反序。

    2-SAT

    2-SAT:有 nn 个变量,每个变量只有两种可能的取值。给定 mm 个条件,每个条件都形如「若 ai=pa_i = p 则 aj=qa_j = q」。求是否存在对 nn 个变量的合法赋值,使得 mm 个条件均得到满足。

    2-SAT 的判定:

    • 建立包含 2n2n 个节点的有向图,ai=0a_i = 0 对应节点 ii,ai=1a_i = 1 对应节点 i+ni + n。
    • 建立条件「若 ai=pa_i = p 则 aj=qa_j = q」在图中的边,令 ai=pa_i = p 所代表的节点向 aj=qa_j = q 所代表的节点连一条有向边。
    • 使用有向图 tarjan 算法求出图中所有的强连通分量。若存在一个 ii 使得 ai=0a_i = 0 与 ai=1a_i = 1 所代表的节点存在于同一个强联通分量中,则没有合法的赋值方案,否则肯定可以找到一组合法的赋值方案。

    2-SAT 求方案:

    • 在缩点后 DAG “ 自底向上 “ 的拓扑序中,若 ai=0a_i = 0 比 ai=1a_i = 1 靠后,则 ai=1a_i = 1 则 ai=0a_i = 0。
    • tarjan 得到的 SCC 编号,即为缩点后 DAG “ 自底向上 “ 的拓扑序。

    F - 图论 二分图

    二分图:若一张无向图的 nn 个节点可以分成 A,BA, B 两个非空无交集合,并且在同一集合内的点之间都没有边相连,那么这张无向图称为一张二分图,A,BA, B 分别称为二分图的左部与右部。

    二分图染色

    二分图判定定理:一张无向图是二分图,当且仅当图中不存在奇环。

    二分图判定定理推论:一张二分图的任意子图为二分图。

    二分图路径长度简单性质:

    • 一张二分图中,任意两点间路径经过的边数奇偶性确定。
    • 一张连通非二分图中,任意两点间路径经过的边数可以是奇数也可以是偶数。

    二分图染色:对整张图进行深度优先遍历,尝试用黑白两种颜色标记图中的节点,当一个节点被标记后,它的所有相邻节点应被标记与它相反的颜色。若标记过程中产生冲突,则说明图中存在奇环。

    int tot, head[N], ver[M * 2], Next[M * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    int col[N];
    
    bool dfs(int u, int color) {
        col[u] = color;
    
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (col[u] == col[v])
                return 0;
            else if (!col[v] && !dfs(v, 3 - color))
                return 0;
        }
    
        return 1;
    }

    二分图匹配

    匹配:一组边的集合 SS,满足任意两条边都没有公共端点。属于 SS 的边被称为匹配边,否则被称为非匹配边。若存在 SS 中的一条边的端点为该点,则称该点为匹配点,否则称该点为非匹配点。

    最大匹配:包含边数最多的一组匹配。

    增广路:若二分图中,存在一条连接两个非匹配点的路径,使得非匹配边和匹配边在该路径上交替出现,则称该路径是匹配 SS 的增广路,也叫交错路。满足

    • 长度 len\mathrm{len} 为奇数。
    • 路径上第 1,3,5,⋯ ,len1, 3, 5, \cdots, \mathrm{len} 条边为非匹配边,路径上第 2,4,6,⋯ ,len−12, 4, 6, \cdots, \mathrm{len} - 1 条边为匹配边。

    增广路的简单性质:若将增广路上所有边的状态取反,得到的新的边集 S′S' 仍然是一组匹配,并且匹配边数加一。故二分图的一组匹配 SS 是最大匹配,当且仅当图中不存在 SS 的增广路。

    完美匹配:给定一张二分图,其左、右部分别为 X,YX, Y,若最大匹配包含 min⁡(∣X∣,∣Y∣)\min(|X|, |Y|) 条匹配边,则称该二分图具有完备匹配。

    多重匹配:给定一张二分图,其左、右部节点数分别为 nl,nrn_l, n_r。从中选出尽量多的边,使第 i(1≤i≤nl)i(1 \leq i \leq n_l) 个左部节点至多与 klikl_i 条选出的边相连,第 j(1≤j≤nr)j(1 \leq j \leq n_r) 个右部节点至多与 krikr_i 条选出的边相连。

    二分图最大匹配:匈牙利算法

    匈牙利算法:初始时,所有边都是非匹配边。匈牙利算法不断寻找增广路,依次给每个左部节点 xx 寻找一个匹配的右部节点 yy,需要满足以下两个条件之一

    • yy 是非匹配点。则 x→yx \to y 构成一条长度为 11 的增广路。
    • yy 与左部点 x′x' 匹配,但从 x′x' 出发能找到另一个右部点 y′y' 与 x′x' 匹配。则 x→y→x′→y′x \to y \to x' \to y' 构成一条增广路。

    匈牙利算法原理:一个节点成为匹配点后,至多因为找到增广路而更换匹配对象,但是绝对不会再变回非匹配点。本质上是贪心。

    匈牙利算法,时间复杂度:O(nm)\mathcal{O}(nm)。

    int tot, head[N], ver[M * 2], Next[M * 2];
    void add_edge(int u, int v) {
        ver[++ tot] = v;    Next[tot] = head[u];    head[u] = tot;
    }
    
    bool vis[N];
    int match[N];
    
    bool dfs(int u) {
        for (int i = head[u]; i; i = Next[i]) {
            int v = ver[i];
            if (vis[v]) continue;
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                return 1;
            }
        }
    
        return 0;
    }
    
    int main() {
        int ans = 0;
        for (int i = 1; i <= nl; i ++) {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) ans ++;
        }
    }

    匈牙利算法求字典序最小的最大匹配:考虑匈牙利算法的流程,是一个左部节点不断地挤掉右部节点已匹配的左部节点的过程。可以考虑按编号从大到小加入左部节点,将左部节点的所有出边从小到大排序,保证优先考虑较小的右部节点,即可求得字典序最小的最大匹配。

    二分图最大匹配:最大流模型

    最大流模型:将源点向左部所有点连一条容量为 11 的边,将右部所有点向汇点连一条容量为 11 的边。将左部向右部的连边容量设为 11。此时该网络的最大流即为最大匹配。

    最大流模型,时间复杂度:使用 Dinic 算法求最大流,时间复杂度为 O(mn)\mathcal{O}(m\sqrt{n})。

    二分图最大带权匹配:KM 算法

    • 待填。

    二分图最大带权匹配:费用流模型

    费用流模型:将源点向左部所有点连一条容量为 11 费用为 00 的边,将右部所有点向汇点连一条容量为 11 费用为 00 的边。将左部向右部的连边容量设为 11 并保持费用不变。此时该网络的最大费用最大流即为最大匹配。

    二分图最大多重匹配:最大流模型

    最大流模型:将源点向左部的节点 i(1≤i≤nl)i(1 \leq i \leq n_l) 连一条容量为 klikl_i 的边,将右部的节点 j(1≤j≤nr)j(1 \leq j \leq n_r) 向汇点连一条容量为 krikr_i 的边。将左部向右部的连边容量设为 11。此时该网络的最大流即为最大多重匹配。

    二分图常用模型

    点覆盖:一组点的集合 SS,满足任意一条边都至少有一个端点属于该点集。

    边覆盖:一组边的集合 SS,满足任意一个点都至少有一条邻边属于该边集。

    独立集:一组点的集合 SS,满足该点集中的点两两没有边。

    团:一组点的集合 SS,满足该点集中的点两两有边。

    二分图中的最小点覆盖(König 定理):在二分图中,最小点覆盖等于最大匹配。

    König 定理证明:对于同一个二分图的任意一个匹配,由于匹配中的边的端点不相交,则匹配中的任意一条边至少有一个端点要在点覆盖中,即任意匹配 ≤\leq 任意点覆盖。现在考虑对最大匹配构造一个点覆盖

    • 对二分图求一个最大匹配。
    • 从左部每个非匹配点出发,再执行一次 DFS 寻找增广路的过程(一定会失败,以匹配边结束),标记路上经过的所有点。
    • 取左部未被标记点,右部标记点,就得到了一组点覆盖。

    上述构造,对点覆盖所包含点数等于最大匹配所包含边数的讨论:

    • 左部非匹配点一定都被标记。因为他们是出发点。
    • 右部非匹配点一定都没被标记。否则就找到了增广路。
    • 一对匹配点要么都被标记,要么都没被标记。因为在找增广路的过程中,左部匹配点只能通过右部到达。

    由于在上述构造中,我们取了左部未标记点,右部标记点。根据对点的讨论可以发现,恰好是每条匹配边取了一个点,所以选出的点数等于最大匹配所包含的边数。

    上述构造,对点覆盖合法性的讨论:

    • 匹配边一定被覆盖。因为恰好有一个端点被取走。
    • 连接两个非匹配点的边一定不存在。否则就有长度为 11 的增广路了。
    • 连接左部非匹配点 ii 与右部匹配点 jj 的边。jj 一定被访问,因为 ii 是出发点,而我们取了所有右部标记点,因此这样的边也被覆盖。
    • 连接左部匹配点 ii 与右部非匹配点 jj 的边。ii 一定没有被访问,否则再走到 jj 就找到了增广路,而我们取了所有左部未被标记点,因此这样的边也被覆盖。

    二分图中的最大独立集:在二分图中,最大独立集与最小点覆盖互补。

    二分图中的最小边覆盖:在二分图中,若不存在独立点,则最小边覆盖等于最大独立集。

    无向图中的最大团:在无向图中,原图的最大团等于其补图的最大独立集。

    有向无环图中的最小不相交路径覆盖:在有向无环图 G=(V,E)G = (V, E) 中,原图 GG 的最小不相交路径覆盖等于 ∣V∣|V| 减去其拆点二分图 G0G_0 的最大匹配。

    • 构造拆点二分图 G0G_0,其左、右部节点数均为 ∣V∣|V|,若 (x,y)∈E(x, y) \in E,则在左部点 xx 与右部点 yy 之间连边。

    Hall 定理

    Hall 定理:一张二分图存在完备匹配,当且仅当对于 1≤k≤∣X∣1 \leq k \leq |X|,均满足从 XX 中选出 kk 个不同点,连向 YY 的点集大小 ≥k\geq k。

    Trick

    树上最大独立集

    • 先选上所有叶子,然后从叶子向上考察每个点能否进入独立集,能选则选。

    F - 图论 网络流

    网络基础

    网络流图:

    • 源点:有且仅有一个点 ss,它的入度为 00,称这个点为源点。
    • 汇点:有且仅有一个点 tt,它的出度为 00,称这个点为汇点。
    • 容量:每一条有向边,均有流量的上限,即容量。

    容量函数 cc:V×V→RV \times V \to \R 的函数,满足

    ∀(u,v)∈E,c(u,v)≥0∀(u,v)∉E,c(u,v)=0\forall (u, v) \in E, c(u, v) \geq 0 \\ \forall (u, v) \notin E, c(u, v) = 0

    流量函数 ff:V×V→RV \times V \to \R 的函数,满足以下条件

    • 容量限制:∀(u,v),f(u,v)≤c(u,v)\forall (u, v), f(u, v) \leq c(u, v)。
    • 斜对称性:∀(u,v),f(u,v)=−f(v,u)\forall (u, v), f(u, v) = -f(v, u)。
    • 流守恒性:从源点流出的流量等于汇点流出的流量,即
    ∀x∈V\{s,t},∑(u,x)∈Ef(u,x)=∑(x,v)∈Ef(x,v)\forall x \in V \backslash \{s, t\}, \sum\limits_{(u, x) \in E} f(u, x) = \sum\limits_{(x, v) \in E} f(x, v)

    或

    ∀x∈V\{s,t},∑(x,y)f(x,y)=0\forall x \in V \backslash \{s, t\}, \sum\limits_{(x, y)} f(x, y) = 0

    饱和弧 / 非饱和弧:在一个可行流中,若一条边的流量等于容量,则称这条边为饱和弧。否则称这条边为非饱和弧。

    零弧:在一个可行流中,若一条边的流量为 00,则称这条边为零弧。

    前向弧 / 后向弧:在一个可行流中,对于一条 s→ts \to t 的路径,与路径方向相同的边称为前向弧。否则称为后向弧。

    剩余容量函数 cfc_f:cf(u,v)=c(u,v)−f(u,v)c_f(u, v) = c(u, v) - f(u, v)。

    残量网络 GfG_f:Gf=(Vf=V,Ef={(u,v),cf(u,v)>0})G_f = (V_f = V, E_f = \{(u, v), c_f(u, v) > 0\})。

    整张网络的流量 ∣f∣|f|:∣f∣=∑vf(s,v)|f| = \sum_v f(s, v)。

    最大流

    增广路:残量网络上 s→ts \to t 的路径,前向弧都是非饱和弧,后向弧都是非零弧。

    EK

    EK:

    • 每次在当前流 ff 的残量网络 GfG_f 上,用 BFS 找到一个最短增广路 (x1=s,x2,⋯ ,xk−1,xk=t)(x_1 = s, x_2, \cdots, x_{k - 1}, x_k = t),将增广路描述成一个流函数 f0f_0:

      • 对于 1≤i<k1 \leq i < k:
      f0(xi,xi+1)=+min⁡1≤j<k{cf(xj,xj+1)}f0(xi+1,xi)=−min⁡1≤j<k{cf(xj,xj+1)}f_0(x_i, x_{i + 1}) = + \min_{1 \leq j < k} \{c_f(x_j, x_{j + 1})\} \\f_0(x_{i + 1}, x_{i}) = - \min_{1 \leq j < k} \{c_f(x_j, x_{j + 1})\}
      • 而其余函数值为 00。
    • 得到一个流量更大的流函数 f′=f+f0f' = f + f_0。

    • 不断重复此过程,直到当前流 ff 的残量网络 GfG_f 上不存在增广路。

    EK 时间复杂度:O(nm2)\mathcal{O}(nm^2)。

    EK 时间复杂度证明:

    • 每次寻找的增广路长度是不降的。
      • 更强结论:∀v∈V,d′(s,v)≥d(s,v)\forall v \in V, d'(s, v) \geq d(s, v)。
    • 增广次数:O(nm)\mathcal{O}(nm)。
      • 每次增广时,cf(u,v)c_f(u, v) 最小的边记作关键边。一条边成为关键边的次数至多为 n−12\frac{n - 1}{2}。
    const int inf = 0x3f3f3f3f;
    
    namespace nw {
        const int Nx = ..., Mx = ...;
    
        int S, T;
    
        int tot = 1, head[Nx], ver[Mx * 2], edge[Mx * 2], Next[Mx * 2];
        void add_edge(int u, int v, int w) {
            ver[++ tot] = v;    edge[tot] = w;    Next[tot] = head[u];    head[u] = tot;
        }
        void add_network(int u, int v, int w) {
            add_edge(u, v, w), add_edge(v, u, 0);
        }
    
        int pre[Nx], mf[Nx];
        bool vis[Nx];
    
        bool bfs() {
            for (int i = S; i <= T; i ++) vis[i] = 0;
        
            std::queue<int> q; while (q.size()) q.pop();
            q.push(S), vis[S] = 1, mf[S] = inf;
        
            while (q.size()) {
                int u = q.front(); q.pop();
        
                for (int i = head[u]; i; i = Next[i]) {
                    int v = ver[i], w = edge[i];
                    if (w > 0 && !vis[v]) {
                        vis[v] = 1, pre[v] = i, mf[v] = std::min(mf[u], w);
                        q.push(v);
        
                        if (v == T) return 1;
                    }
                }
            }
        
            return 0;
        }
    
        int EK() {
            int max_flow = 0;
            while (bfs()) {
                max_flow += mf[T];
                for (int x = T; x != S; x = ver[pre[x] ^ 1])
                    edge[pre[x]] -= mf[T], edge[pre[x] ^ 1] += mf[T];
            }
        
            return max_flow;
        }
    }

    Dinic

    Dinic:本质和 EK 相同,但优化了寻找增广路的过程。

    • 分层图优化:Dinic 算法首先对图进行一次 BFS,然后在 BFS 生成的分层图中进行多次 DFS。这样就切断了原图中许多不必要的连接,可以进行多路增广,减少了调用增广函数的次数。
    • 不完全 BFS 优化:在 BFS 到汇点 tt 之后就可以停止了,因为后面的路径一定更长。
    • 当前弧优化:每次 DFS 完,找到容量最小的一条边。在这条边之前的路径容量 ≥\geq 这条边的容量,可能会引出其他的增广路。这样的话,在找到第一条增广路后,回溯到容量最小边的起点时,可以避免继续枚举已经流满的容量最小边。
    • 点优化:在同一次 DFS 中,如果一个点引发不出任何的增广路,可以将该点在层次图中抹去。

    Dinic 时间复杂度:O(n2m)\mathcal{O}(n^2m)。

    Dinic 时间复杂度证明:

    • 在一张分层图上,执行 DFS 的次数最多为 O(m)\mathcal{O}(m)。
    • 建立分层图的次数不超过 n−1n - 1。
      • 每轮增广后,残量网络的 d(s,t)d(s, t) 严格单调递增。
    const int inf = 0x3f3f3f3f;
    
    namespace nw {
        const int Nx = ..., Mx = ...;
    
        int S, T;
    
        int tot = 1, head[Nx], ver[Mx * 2], edge[Mx * 2], Next[Mx * 2];
        void add_edge(int u, int v, int w) {
            ver[++ tot] = v;    edge[tot] = w;    Next[tot] = head[u];    head[u] = tot;
        }
        void add_network(int u, int v, int w) {
            add_edge(u, v, w), add_edge(v, u, 0);
        }
    
        int lev[Nx];
        int cur[Nx];
    
        bool bfs() {
            for (int i = S; i <= T; i ++) cur[i] = head[i];
            for (int i = S; i <= T; i ++) lev[i] = 0;
    
            std::queue<int> q; while (q.size()) q.pop();
            q.push(S), lev[S] = 1;
    
            while (q.size()) {
                int u = q.front(); q.pop();
    
                for (int i = head[u]; i; i = Next[i]) {
                    int v = ver[i], w = edge[i];
                    if (w > 0 && !lev[v]) {
                        lev[v] = lev[u] + 1;
                        q.push(v);
    
                        if (v == T) return 1;
                    }
                }
            }
    
            return 0;
        }
    
        int dfs(int u, int flow) {
            if (u == T) return flow;
    
            int res = 0;
            for (int &i = cur[u]; i; i = Next[i]) {
                int v = ver[i], w = edge[i];
                if (w > 0 && lev[u] < lev[v]) {
                    int delta = dfs(v, std::min(w, flow - res));
                    if (delta) {
                        edge[i] -= delta, edge[i ^ 1] += delta;
                        res += delta;
        
                        if (res == flow) break;
                    }
                }
            }
    
            if (res < flow) lev[u] = 0;
            return res;
        }
    
        int dinic() {
            int max_flow = 0;
            while (bfs()) max_flow += dfs(S, inf);
    
            return max_flow;
        }
    }

    常用模型

    限制点的流量:可以考虑将点拆成「入点」与「出点」,从入点向出点连一条有容量的边。

    最小割

    割:在图 G=(V,E)G = (V, E) 上,对于某个点集 P⊆VP \subseteq V,割 (P,V\P)(P, V \backslash P) 定义为

    (P×(V\P))⋂E(P \times (V \backslash P)) \bigcap E

    割的容量:割包含的边的容量之和,即

    c(P,V\P)=∑u∈P∑v∈V\Pc(u,v)c(P, V \backslash P) = \sum\limits_{u \in P}\sum\limits_{v \in V \backslash P} c(u, v)

    s→ts \to t 割:满足 s∈Ps \in P 且 t∈V\Pt \in V \backslash P 的割。

    最大流与最小割:在一张网络中,最大流等于最小割。

    最大流与最小割证明:对于同一个网络的任意一个流 ff 和任意一个 s→ts \to t 割 (S,T)(S, T),均有

    ∣f∣=∑u∈S∑v∈Tf(u,v)≤∑u∈S∑v∈Tc(u,v)=c(S,T)|f| = \sum\limits_{u \in S}\sum\limits_{v \in T} f(u, v) \leq \sum\limits_{u \in S} \sum\limits_{v \in T} c(u, v) = c(S, T)

    即任意流 ≤\leq 任意割。考虑 EK 算法求得的流 ff,记流 ff 对应的残量网络中从 ss 出发可达的所有点组成的点集为 SS,不可达的所有点组成的点集为 TT,由于找不到流 ff 的增广路,故 (S,T)(S, T) 是一个 s→ts \to t 割,且由残量网络的定义可得 ∣f∣=c(S,T)|f| = c(S, T)。故最大流等于最小割。

    最小割的可行边(并)与必经边(交):

    • 可行边:一条边 (u,v,w)(u, v, w) 是最小割可行边,当且仅当这条边满流,且 GfG_f 不存在 u→vu \to v 的路径(u,vu, v 不在同一个强连通分量内)。
    • 必经边:一条边 (u,v,w)(u, v, w) 是最小割必经边,当且仅当这条边满流,且 GfG_f 上存在 s→us \to u 和 v→tv \to t 的路径(uu 和 ss 在同一个强连通分量内,vv 和 tt 在同一个强连通分量内)。

    常用模型

    二选一模型:有 nn 个任务,每个任务可以在机器 AA 或机器 BB 上完成,花费分别为 aia_i 和 bib_i。有 mm 对二元关系 (xi,yi)(x_i, y_i),若第 xix_i 个任务与第 yiy_i 个任务不在同一个机器上完成,则增加 viv_i 的花费。求最小总花费。

    • 模型构造:

      • 建源点 ss 与汇点 tt,每个任务都建一个点,标号 1∼n1 \sim n。
      • SS 向第 ii 个任务连一条容量为 aia_i 的边,第 ii 个任务向 TT 连一条容量为 bib_i 的边。
      • 对于每个二元关系 (xi,yi)(x_i, y_i),在第 xix_i 个任务与第 yiy_i 个任务间连一条容量为 viv_i 的双向边。
    • 模型分析:

      • 第 ii 个任务在机器 AA 上完成,就要割去边权为 aia_i 的边。第 ii 个任务在机器 BB 上完成,就要割去边权为 bib_i 的边。
      • 对于每个二元关系 (xi,yi)(x_i, y_i),若 xi,yix_i, y_i 没有被分配到同一个机器,就要割去边权为 viv_i 的边。

    闭合子图:一个有向图 G=(V,E)G = (V, E) 的闭合子图,是该有向图的一个子图,且该子图内点集的所有出边都指向该点集。

    最大权闭合子图:点权和最大的闭合子图。

    最大权闭合子图模型:有 nn 个事件,事件发生会带来收益 wiw_i,wiw_i 可正可负,一个事件发生的前提是指定的若干事件必须发生。求最优的确定所有事件是否发生的方案,使得收益最大。

    • 模型构造:
      • 建源点 ss 与汇点 tt,对每个事件都建一个点,标号 1∼n1 \sim n。
      • 若 wi>0w_i > 0,则令 SS 向 ii 连一条容量为 wiw_i 的边;若 wi<0w_i < 0,则令 ii 向 TT 连一条容量为 −wi-w_i 的边。
      • 对于原图中的边,容量设为 +∞+\infty。
    • 模型分析:最大权闭合子图 == 正点权和 −- 最小割。
      • 在一个割中割去的边,负权点表示选择,正权点表示不选。
      • 可以证明,在一个割中,已割去的负权点与未割去的正权点组成的子图 WW 与原图的闭合子图对应。如果 WW 不是闭合子图,出边可能指向已割去的正权点或未割去的负权点。若为前者,则 WW 内的流越过了这个割;若为后者,则 WW 内的流可以流向汇点。

    费用流

    EK & Dinic:每次需要扩展一条费用最小的增广路。

    const int inf = 0x3f3f3f3f;
    
    namespace nw {
        const int Nx = ..., Mx = ...;
    
        int S, T;
    
        int tot = 1, head[Nx], ver[Mx * 2], Next[Mx * 2]; int edge[Mx * 2], cost[Mx * 2];
        void add_edge(int u, int v, int w, int c) {
            ver[++ tot] = v;    edge[tot] = w;    cost[tot] = c;    Next[tot] = head[u];    head[u] = tot;
        }
        void add_network(int u, int v, int w, int c) {
            add_edge(u, v, w, +c), add_edge(v, u, 0, -c);
        }
    
        int max_flow, min_cost;
    
        int dist[Nx];
        bool exist[Nx];
    
        int cur[Nx];
        bool vis[Nx];
    
        bool spfa() {
            for (int i = S; i <= T; i ++) cur[i] = head[i], vis[i] = 0;
            for (int i = S; i <= T; i ++) dist[i] = inf;
    
            std::queue<int> q;
            q.push(S), dist[S] = 0;
    
            while (q.size()) {
                int u = q.front(); q.pop(); exist[u] = 0;
    
                for (int i = head[u]; i; i = Next[i]) {
                    int v = ver[i], w = edge[i], c = cost[i];
                    if (w > 0 && dist[u] + c < dist[v]) {
                        dist[v] = dist[u] + c;
                        if (!exist[v]) {
                            exist[v] = 1;
                            q.push(v);
                        }
                    }
                }
            }
    
            return dist[T] < inf;
        }
    
        int dfs(int u, int flow) {
            if (u == T) {
                min_cost += flow * dist[T];
                return flow;
            }
    
            vis[u] = 1;
    
            int res = 0;
            for (int &i = cur[u]; i; i = Next[i]) {
                int v = ver[i], w = edge[i], c = cost[i];
                if (w > 0 && !vis[v] && dist[u] + c == dist[v]) {
                    int delta = dfs(v, std::min(w, flow - res));
                    if (delta) {
                        edge[i] -= delta, edge[i ^ 1] += delta;
                        res += delta;
        
                        if (res == flow) break;
                    }
                }
            }
    
            if (res == flow) vis[u] = 0;
            return res;
        }
    
        void dinic() {
            max_flow = 0, min_cost = 0;
            while (spfa()) max_flow += dfs(S, inf);
        }
    }