图论

图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形。

存图方式

用 $n$ 代指图的点数，用 $m$ 代指图的边数。

邻接表

使用一个支持动态增加元素的数据结构构成的数组来存边，其中 adj[u] 存储的是点 $u$ 的所有出边的相关信息（终点、边权等）。

1
2
3
4
5
6
7
8
9
10
11
12
struct edge {
    int v, w;
};

int n, m;
cin >> n >> m;
vector<vector<edge>> adj(n + 1);
for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
}

拓扑排序

拓扑排序要解决的问题是如何给一个有向无环图的所有节点排序，并保证每个点都在其后继节点之前。

Kahn 算法

若 $tfn$ 元素数小于节点数则原 DAG 存在环，若任意时刻不存在两个入度为 0 的节点则拓扑序列唯一。

Kahn 算法同样可以为无向图判环，在判断无向图中是否存在环时，是将所有 度 <= 1 的结点入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> tfn; // 拓扑序列  
queue<int> q;  
for (int u = 1; u <= n; u++) {  
    if (deg[u]) continue;  
    q.push(u), tfn.push_back(u);  
}  
while (!q.empty()) {  
    int u = q.front();  
    q.pop();  
    for (auto v: adj[u]) {  
        if (--deg[v]) continue;  
        q.push(v), tfn.push_back(v);  
    }  
}

DFS 算法

拓扑排序实际上是 DFS 后序遍历的逆序，因此可以使用 DFS 实现拓扑排序。

如果需要按拓扑序 DP 或其它操作，可以直接按 DFS 后序遍历顺序执行转移，如果需要判环需要额外记录 ins 表示节点是否在搜索路径中。

1
2
3
4
5
6
7
8
9
vector<int> tfn, vis(n + 1);  
auto dfs = [&](auto &&self, int u) -> void {  
    if (vis[u]) return;  
    tfn.push_back(u);  
    for (int v: adj[u]) {  
        self(self, v);  
    }  
};  
for (int u = 1; u <= n; u++) dfs(dfs, u);

最短路

Floyd 算法

Floyd 算法是一个基于动态规划的全源最短路算法，能确定某张图是否存在负环，并确定那些不受负环影响的顶点对之间的最短路。时间复杂度 $\Theta(n^3)$ ，空间复杂度 $\Theta(n^2)$ 。

若存在任意节点 $i$ 满足 $f[i][i]<0$，则图中存在负环，可达节点 $i$ 的节点均不存在最短路。

1
2
3
4
5
6
7
8
vector<vector<int> > f = adj; // adj 为存储邻居节点最短边权的邻接矩阵
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
    }
}

bitset 优化求传递闭包

Floyd 传递闭包算法通过动态规划逐步枚举中间节点，在 $\Theta(n^3)$ 时间内计算出有向图中所有点对的可达性。

使用 bitset 优化后复杂度为 $\Theta\left( \frac{n^3}{w} \right)$ ，其中 $w=64$ 为计算机位宽。

$adj$ 为使用 bitset 表示的邻接矩阵，初始化时注意自身节点永远可达。

1
2
3
4
5
6
7
constexpr int maxn = 2000;  
vector<bitset<maxn> > reach = adj;
for (int k = 1; k <= n; k++) {  
    for (int u = 1; u <= n; u++) {  
        if (reach[u][k]) reach[u] |= reach[k];  
    }  
}

SPFA 算法

SPFA 算法即队列优化的 Bellman–Ford 算法，是一种基于松弛操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断，最坏情况下时间复杂度为 $O(nm)$ 。

通过记录最短路经过了多少条边，SPFA 可以用于判断从 $s$ 点出发是否能抵达一个负环，当经过了至少 $n$ 条边时，函数返回 false，从 $s$ 点出发可以抵达一个负环。

如果需要判断图是否存在负环，需要建立超级源点，即向图上每个节点连一条权值为 $0$ 的边，然后以超级源点为起点执行 SPFA 算法，注意此时需要判断的边数为 $n+1$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> dis(n + 1, inf), cnt(n + 1);  
auto spfa = [&](int s) {  
    queue<int> q;  
    dis[s] = 0, q.push(s);  
    while (!q.empty()) {  
        auto u = q.front();  
        q.pop();  
        for (auto [v, w]: adj[u]) {  
            if (dis[u] + w >= dis[v]) continue;  
            dis[v] = dis[u] + w;  
            cnt[v] = cnt[u] + 1;  
            if (cnt[v] >= n) return false;  
            q.push(v);  
        }  
    }  
    return true;  
};

Dijkstra 算法

Dijkstra 算法是一种求解非负权图上单源最短路径的算法，每轮从未确定最短路的节点中选取一个最短路长度最小的结点（其最短路已经确定）执行松弛。

以下代码使用优先队列实现，不使用 vis 数组，时间复杂度 $O((n+m)\log{m})$ 。

注意保证入队判断和出队判断一致且正确，否则会出现时间复杂度错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> dis(n + 1, inf);  
auto dijkstra = [&](int s) {  
    priority_queue<pair<int, int> > pq;  
    dis[s] = 0;  
    pq.emplace(0, s);  
    while (!pq.empty()) {  
        auto [d, u] = pq.top();  
        d = -d;  
        pq.pop();  
        if (d > dis[u]) continue;  
        for (auto [v, w]: adj[u]) {  
            if (dis[u] + w >= dis[v]) continue;  
            dis[v] = dis[u] + w;  
            pq.emplace(-dis[v], v);  
        }  
    }  
};

Johnson 算法

新建一个虚拟节点（设其编号为 $0$ ）。从这个点向其他所有点连一条边权为 $0$ 的边，然后用 SPFA 求出 $0$ 号点到其它所有点的最短路作为势能函数，然后根据势能函数重新标注边权使边权非负，然后就可以跑 $n$ 轮 Dijkstra 计算最短路，时间复杂度 $O(nm\log{m})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> h(n + 1, inf);
vector dis(n + 1, vector(n + 1, inf));
// SPFA and Dijkstra
auto johnson = [&]() {  
    if (!spfa(0)) return false;  
    for (int u = 1; u <= n; u++) {  
        for (auto &[v, w]: adj[u]) {  
            w = w + h[u] - h[v];  
        }  
    }  
    for (int u = 1; u <= n; u++) {  
        dijkstra(u);  
        for (int v = 1; v <= n; v++) {  
            if (dis[u][v] == inf) continue;  
            dis[u][v] = dis[u][v] + h[v] - h[u];  
        }  
    }  
    return true;  
};

生成树

生成树是一个无向连通图的子图，它的边连接原图所有顶点，同时不形成任何环。

最小生成树

最小生成树（MST）是边权和最小的生成树。

瓶颈生成树是的最大的边权值最小的生成树，最小生成树是瓶颈生成树的充分不必要条件。

Kruskal 算法

Kruskal 算法是一种贪心算法，通过按边权从小到大排序并依次选择不构成环的边来构造最小生成树。

如果某个权值的边中，实际放的条数比可以放的条数少，那么就说明这几条边与之前的边产生了一个环，即最小生成树不唯一。

以下代码使用并查集判环，其中 cnt 为当前连通块个数。Kruskal 部分时间复杂度为 $O(m\alpha(n))$，总时间复杂度 $O(m\log{m})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
vector<tuple<int, int, int>> edges;  
auto kruskal = [&]() {  
    DSU dsu(n + 1);  
    int sum = 0, cnt = n;  
    sort(ed.begin(), ed.end());  
    for (auto &[w, u, v]: ed) {  
        if (dsu.merge(u, v) == -1) continue;  
        sum += w;  
        if (--cnt == 1) break;  
    }  
    return cnt == 1 ? sum : -1;  
};

Prim 算法

Prim 算法是一种贪心算法，其核心思想是从任意节点开始，逐步选择与当前生成树相连且权值最小的边，直到连通块覆盖所有节点。

其在稠密图或边具有较多特殊性质的问题中具有优势，易于结合数据结构优化。

以下代码使用优先队列实现，其中 cnt 为当前连通块的大小，时间复杂度为 $O((n+m)\log{m})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto prim = [&]() {  
    vector<char> vis(n + 1);  
    priority_queue<pair<int, int> > pq;  
    pq.emplace(0, 1);  
    int sum = 0, cnt = 0;  
    while (!pq.empty() && cnt < n) {  
        auto [d, u] = pq.top();  
        d = -d;  
        pq.pop();  
        if (vis[u]) continue;  
        vis[u] = true;  
        sum += d, cnt++;  
        for (auto &[v, w]: adj[u]) {  
            if (vis[v]) continue;  
            pq.emplace(-w, v);  
        }  
    }  
    return cnt == n ? sum : -1;  
};

Boruvka 算法

Boruvka 算法通过多轮迭代，每轮为每个连通分量寻找最优边合并连通分量，在 $O(\log{n})$ 轮内求解最小生成树。

其在稠密图或边具有较多特殊性质的问题中具有优势，易于结合数据结构优化。

以下代码使用 01Trie 优化，求解边权为 $a{i} \operatorname{xor} a{j}$ 的完全图的最小生成树，时间复杂度为 $O(n\log{n}\log{V})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
DSU dsu(n);
bool upd = true;  
int sum = 0, cnt = 0;  
while (upd) {  
    upd = false;  
    vector<vector<int>> b(n);  
    vector<tuple<int, int, int>> ed(n, {inf, -1, -1});  
    for (int i = 0; i < n; i++) if (dsu.p[i] < 0) b[i].reserve(-dsu.p[i]);  
    for (int i = 0; i < n; i++) b[dsu.find(i)].push_back(i);  
    for (int i = 0; i < n; i++) {  
        for (auto x : b[i]) trie.insert(rt, a[x], -1);  
        for (auto x : b[i]) {  
            int y = -1;  
            trie.query(rt, a[x], y);  
            ed[i] = min(ed[i], {a[x] ^ a[y], x, y});  
        }  
        for (auto x : b[i]) trie.insert(rt, a[x], 1);  
    }  
    for (int i = 0; i < n; i++) {  
        auto &[w, u, v] = ed[i];  
        if (u == -1) continue;  
        if (dsu.merge(u, v) == -1) continue;  
        sum += w, cnt++;  
        upd = true;  
    }  
}

斯坦纳树

给定正权连通图中的 $n$ 个点与 $k$ 个关键点，连接 $k$ 个关键点，使得所有边的权值和最小的生成树就是斯坦纳树。

我们使用状态压缩动态规划来求解. 用 $dp_{i,s}$ 表示以 $i$ 为根的一棵树，包含集合 $s$ 中所有点的最小边权值和.

  • 首先对连通的子集进行转移： $dp{i,s} \leftarrow \min(dp{i,s}, dp{i,t} + dp{i,s-t})$，通过二进制位运算枚举真子集 $t$ 转移。
  • 在当前的子集连通状态下进行边的松弛操作： $dp{i,s} \leftarrow \min(dp{i,s}, dp_{j,s}+ w(i, j))$ ，使用 Dijkstra 实现即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lim = 1 << k;  
vector dp(lim, vector(n + 1, infl));  
for (int i = 0; i < k; i++) dp[1 << i][p[i]] = 0;  
for (int s = 1; s < lim; s++) {  
    for (int i = 1; i <= n; i++) {  
        for (int t = s - 1 & s; t > 0; t = t - 1 & s) {  
            dp[s][i] = min(dp[s][i], dp[t][i] + dp[s ^ t][i]);  
        }  
    }  
    priority_queue<pair<i64, int> > pq;  
    for (int i = 1; i <= n; i++) pq.emplace(-dp[s][i], i);  
    while (!pq.empty()) {  
        auto [d, u] = pq.top();  
        d = -d;  
        pq.pop();  
        if (d > dp[s][u]) continue;  
        for (auto [v, w]: adj[u]) {  
            if (dp[s][u] + w >= dp[s][v]) continue;  
            dp[s][v] = dp[s][u] + w;  
            pq.emplace(-dp[s][v], v);  
        }  
    }  
}

连通性相关算法

图论中的连通性研究图中节点间的可达性关系，包括无向图的双连通分量、有向图的强连通分量、割点/桥等概念。

Tarjan 算法

Tarjan 算法其基于对图进行 DFS 得到的搜索树，可以用于求各种连通分量，时间复杂度为 $O(n+m)$ 。

搜索树中有 $4$ 种边（不一定全部出现）：

  1. 树边：搜索树中的边。
  2. 反祖边：指向祖先结点的边。
  3. 横叉边：指向某祖先已访问完毕的的另一个子树的边。
  4. 前向边：指向子树的边。

由每个返祖边都对应一个基本环等性质，在搜索过程中，维护 DFS 序表示的时间戳 $dfn$ 等信息，即可求得所需的联通分量或割点/桥。

割点

对于一个无向图，如果删掉一个节点后图中的连通分量数增加了，则称这个节点为割点或者割顶。

由于无向图的搜索树不存在横叉边，任何的非树边在搜索树上都具有祖先 - 后代关系，容易得出若非根结点 $u$ 的子树不存在任何一个点可以到达其祖先，则该点是割点。

定义 $f{u}$​ 表示与 $u$ 通过返祖边相连的所有点的时间戳的最小值，$low[u]$ 为子树 $u$ 中 $f{u}$​ 的最小值（下文中 $low$ 均为此定义），对非根结点只需要判断是否存在子树 $v$ 满足 $low[v] \ge dfn[u]$ ，即可判断是否为割点。

对于根节点，只需要判断是否有两个儿子即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int id = 0;  
vector<int> dfn(n + 1), low(n + 1), cut(n + 1);  
auto tarjan = [&](auto &&self, int u, int fa) -> void {  
    low[u] = dfn[u] = ++id;  
    int ch = 0;  
    for (auto v: adj[u]) {  
        if (v == fa) continue;  
        if (!dfn[v]) {  
            ch++;  
            self(self, v, u);  
            low[u] = min(low[u], low[v]);  
            if (fa && low[v] >= dfn[u]) cut[u] = true;  
        } else {  
            low[u] = min(low[u], dfn[v]);  
        }  
    }  
    if (!fa && ch >= 2) cut[u] = true;  
};  
for (int u = 1; u <= n; u++) {  
    if (!dfn[u]) tarjan(tarjan, u, 0);  
}

割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。

求法和割点类似，只需要将判断条件改为 $low[v] \gt dfn[u]$ ，而且不需要考虑根节点的问题。

以下实现中 $bri[u] = true$ 表示 (fa[u], u) 为一条割边，每条边上有唯一正编号 $i$ 以处理重边 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int id = 0;  
vector<int> dfn(n + 1), low(n + 1), bri(n + 1);  
auto tarjan = [&](auto &&self, int u, int li) -> void {  
    low[u] = dfn[u] = ++id;  
    for (auto [v, i]: adj[u]) {  
        if (i == li) continue;  
        if (!dfn[v]) {  
            self(self, v, i);  
            low[u] = min(low[u], low[v]);  
            if (low[v] > dfn[u]) bri[v] = true;  
        } else {  
            low[u] = min(low[u], dfn[v]);  
        }  
    }  
};  
for (int u = 1; u <= n; u++) {  
    if (!dfn[u]) tarjan(tarjan, u, 0);  
}

边双连通分量

在一个无向图中，对于两个点 $u$ 和 $v$，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 $u$ 和 $v$ 边双连通。

边双连通分量（BCC）是一个极大的强连通子图，而无向图边连通指图中任意两个结点边双连通。

在回溯的过程中，判定 $dfn[u]=low[u]$ 是否成立（即无法通过子树回到祖先），如果成立，则栈中 $u$ 及其上方的结点构成一个边双连通分量。

以下实现中，$bcc[u]$ 表示 $u$ 所属的边双连通分量编号，$sz[s]$ 表示边双连通分量 $s$ 的大小，注意每条边上定义了唯一正编号 $i$ 以处理重边，因为初始时传入了 $0$ 作为无效编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int id = 0, bc = 0;  
stack<int> stk;  
vector<int> dfn(n + 1), low(n + 1), bcc(n + 1), sz(n + 1);  
auto tarjan = [&](auto &&self, int u, int li) -> void {  
    low[u] = dfn[u] = ++id, stk.push(u);  
    for (auto [v, i]: adj[u]) {  
        if (i == li) continue;  
        if (!dfn[v]) {  
            self(self, v, i);  
            low[u] = min(low[u], low[v]);  
        } else {  
            low[u] = min(low[u], dfn[v]);  
        }  
    }  
    if (dfn[u] == low[u]) {  
        int v;  
        ++bc;  
        do {  
            v = stk.top();  
            stk.pop();  
            bcc[v] = bc;  
            sz[bc]++;  
        } while (v != u);  
    }  
};  
for (int u = 1; u <= n; u++) {  
    if (!dfn[u]) tarjan(tarjan, u, 0);  
}

强连通分量

强连通分量（SCC）是一个极大的强连通子图，而有向图强连通指图中任意两个结点连通。

实现和 BCC 类似，但是有向图存在横叉边，需要额外定义 $ins$ 数组表示节点是否在当前搜索路径上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int id = 0, sc = 0;  
stack<int> stk;  
vector<int> dfn(n + 1), low(n + 1), scc(n + 1), sz(n + 1), ins(n + 1);  
auto tarjan = [&](auto &&self, int u) -> void {  
    low[u] = dfn[u] = ++id, stk.push(u), ins[u] = 1;  
    for (auto v: adj[u]) {  
        if (!dfn[v]) {  
            self(self, v);  
            low[u] = min(low[u], low[v]);  
        } else if (ins[v]) {  
            low[u] = min(low[u], dfn[v]);  
        }  
    }  
    if (dfn[u] == low[u]) {  
        int v;  
        ++sc;  
        do {  
            v = stk.top();  
            stk.pop();  
            scc[v] = sc;  
            sz[sc]++;  
            ins[v] = 0;  
        } while (v != u);  
    }  
};  
for (int u = 1; u <= n; u++) {  
    if (!dfn[u]) tarjan(tarjan, u);  
}

缩点

利用 Tarjan 算法求出的连通分量可以执行缩点，获得一个新的图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> ca(sc + 1);  
vector<vector<int> > cadj(sc + 1);  
for (int u = 1; u <= n; u++) {  
    ca[scc[u]] += a[u]; // 统计连通分量信息
    for (auto v: adj[u]) {  
        if (scc[u] != scc[v]) {  
            cadj[scc[u]].push_back(scc[v]); // 在新图连边
        }  
    }  
}  
// 以下为去重逻辑，需根据实际情况修改
for (int i = 1; i <= sc; i++) {  
    ranges::sort(cadj[i]);  
    cadj[i].erase(ranges::unique(cadj[i]).begin(), cadj[i].end());  
}

最近公共祖先

最近公共祖先简称 LCA ，即公共祖先里面，离根最远的那个。

树上任何两点之间的路径均可以从 LCA 断开分为至多两个深度单调的路径，可以结合树上前缀和/差分计算路径信息，也可以使用数据结构维护。

倍增算法

通过 dfs 预处理出每个节点第 $2^{i}$ 祖先节点，可求两节点间最近公共祖先 (LCA)。

树上两点之间路径的信息可以在倍增算法求 LCA 的过程中同时处理，如路径长度，只要求结合律。

倍增算法的预处理时间复杂度为 $O(n\log n)$ ，单次查询时间复杂度为 $O(\log n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 最大深度，视题目范围确定，也可直接取30
constexpr int maxd = (int) bit_width(100000ull);

vector<int> dep(n + 1);
vector<array<int, maxd> > fa(n + 1);
vector<array<i64, maxd> > cost(n + 1);
auto dfs = [&](auto &&self, int u) -> void {
    dep[u] = dep[fa[u][0]] + 1;
    for (int i = 1; i < maxd; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        cost[u][i] = cost[fa[u][i - 1]][i - 1] + cost[u][i - 1];
    }
    for (auto [v, w]: adj[u]) {
        if (v == fa[u][0]) continue;
        fa[v][0] = u, cost[v][0] = w;
        self(self, v);
    }
};
dfs(dfs, 1);

auto lca = [&](int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
	i64 ans = 0;
    int tmp = dep[y] - dep[x];
    for (int j = 0; tmp; j++, tmp >>= 1)
        if (tmp & 1) ans += cost[y][j], y = fa[y][j];
    if (y == x) return ans; // 此时 x 与 y 均为最近公共祖先
    for (int j = maxd - 1; j >= 0; j--) {
        if (fa[x][j] == fa[y][j]) continue;
        ans += cost[x][j] + cost[y][j];
        x = fa[x][j], y = fa[y][j];
    }
    ans += cost[x][0] + cost[y][0];
    return ans; // 此时 x 或 y 的父节点为最近公共祖先
};

转化为 RMQ 问题

由欧拉序的性质，介于欧拉序中 $u$ 任意出现位置 和 $v$ 任意出现位置之间，且深度最小的节点 $k$， 就是 $u$ 和 $v$ 的 LCA 。

也可以使用常数更小，实现更简单的普通的 DFS 序 $dfn$ 转化。不妨设 $dfn{u}​<dfn{v}$ ​，若 $u \neq v$，则它们的 LCA 等于 DFS 序上位置在 $(dfn{u}​,dfn{v}]$ 的深度最小的任意结点的父亲。

由于在 DFS 中，祖先先于后代遍历，所以 $k$ 总是先于 $u$ 和 $v$ 被访问，因此在以上两种转化的实现中，均不需要记录深度。

以下为使用 DFS 序转化为 RMQ 问题求 LCA 的实现，直接在 RMQ 的最底层记录父亲，比较时取 $dfn$ 更小的结点，避免了记录每个结点的父亲 $fa$ 和深度 $dep$ ，时间复杂度瓶颈取决于选择的 RMQ 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int id = 1;  
vector<int> dfn(n + 1), fa(n + 1), val(n + 1);  
iota(val.begin(), val.end(), 0);  
auto dfs = [&](auto &&self, int u) -> void {  
    dfn[u] = id++, val[dfn[u]] = fa[u];  
    for (int v: adj[u]) {  
        if (fa[u] == v) continue;  
        fa[v] = u;  
        self(self, v);  
    }  
};  
dfs(dfs, s);  
  
SparseTable rmq(val, [&](int x, int y) {  
    return dfn[x] < dfn[y];  
});  
  
auto lca = [&](int u, int v) {  
    if (u == v) return u;  
    if (dfn[u] > dfn[v]) swap(u, v);  
    return rmq.query(dfn[u], dfn[v]);  
};

点分治

选择一个节点作为根节点 $rt$，所有完全位于其子树中的路径可以分为两种，一种是经过当前根节点的路径，一种是不经过当前根节点的路径。

对于经过当前根节点的路径，又可以分为两种，一种是以根节点为一个端点的路径，另一种是两个端点都不为根节点的路径。而后者又可以由两条属于前者链合并得到。所以，对于枚举的根节点 $rt$，我们先计算在其子树中且经过该节点的路径对答案的贡献，再递归其子树对不经过该节点的路径进行求解。

若我们 每次选择子树的重心作为根节点，可以保证递归层数最少，时间复杂度为 $O(n\log{n})$ 。

以下代码使用点分治求解树上距离为 $k$ 的点对个数，在一次点分治中处理多个询问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
vector<char> vis(n + 1);  
vector<int> cnt(mxk + 1);  
function<void(int)> divide = [&](int cu) -> void {  
    vector<int> sz(n + 1);  
    auto dfs = [&](auto &&self, int u, int f) -> void {  
        sz[u] = 1;  
        for (auto [v, w]: adj[u]) {  
            if (f == v || vis[v]) continue;  
            self(self, v, u);  
            sz[u] += sz[v];  
        }  
    };  
    dfs(dfs, cu, 0);  
  
    int tot = sz[cu], mxs = inf;  
    auto getc = [&](auto &&self, int u, int f) -> void {  
        int cs = 0;  
        for (auto [v, w]: adj[u]) {  
            if (f == v || vis[v]) continue;  
            self(self, v, u);  
            cs = max(cs, sz[v]);  
        }  
        cs = max(cs, tot - sz[u]);  
        if (cs < mxs) mxs = cs, cu = u;  
    };  
    getc(getc, cu, 0);  
    vis[cu] = true;  
  
    cnt[0] = 1;  
    vector<int> dis;  
    for (auto [rv, rw]: adj[cu]) {  
        if (vis[rv]) continue;  
        int st = dis.size();  
        auto getd = [&](auto &&self, int u, int f, int d) -> void {  
            for (auto [v, w]: adj[u]) {  
                if (d > mxk) continue;  
                dis.push_back(d);  
                if (f == v || vis[v]) continue;  
                self(self, v, u, d + w);  
            }  
        };  
        getd(getd, rv, 0, rw);  
  
        for (int i = st; i < dis.size(); i++) {  
            for (auto &[k, a]: qry) {  
                int r = k - dis[i];  
                if (r < 0) continue;  
                a += cnt[r];  
            }  
        }  
        for (int i = st; i < dis.size(); i++) cnt[dis[i]]++;  
    }  
    for (int d: dis) cnt[d]--;  
  
    for (auto [v, w]: adj[cu]) {  
        if (!vis[v]) divide(v);  
    }  
};  
divide(1);

欧拉图

欧拉图是存在经过每条边恰好一次的回路（欧拉回路）或路径（欧拉通路）的图，后者又称欧拉半图。

有向图存在欧拉回路当且仅当强连通且所有顶点入度等于出度；存在欧拉路径当且仅当弱连通，且除起点（出度 = 入度 + 1）和终点（入度 = 出度 + 1）外，其余顶点入度等于出度。

无向图存在欧拉回路当且仅当连通且所有顶点度数为偶数；存在欧拉路径当且仅当连通且恰有两个奇数度顶点（起点和终点）。

Hierholzer 算法

Hierholzer 算法是用于在欧拉图中找出欧拉回路/路径的算法，其核心思想是 DFS 遍历边并在回溯时记录节点。

以下实现使用后序遍历和邻接表删除已访问边的方式实现 Hierholzer 算法，最后反转结果得到正确的访问顺序，如需字典序最小则需要保证起点正确且邻接表被倒序排序，时间复杂度 $O(m)$ 。

1
2
3
4
5
6
7
8
9
10
11
vector<int> ans;  
auto dfs = [&](auto &&self, int u) -> void {  
    while (!adj[u].empty()) {  
        int v = adj[u].back();  
        adj[u].pop_back();  
        self(self, v);  
    }  
    ans.push_back(u);  
};  
dfs(dfs, st);  
ranges::reverse(ans);

树的序

通过各种方法，可以将树上问题转化为序列问题解决。

欧拉序

欧拉序又称全 DFS 序，是对树进行 DFS 时，按访问顺序依次记录节点所得到的序列，每个节点在入栈和出栈时各被记录一次。

树的欧拉序结合 RMQ 可以高效解决 LCA（最近公共祖先）问题，并支持子树和路径查询（需要树上差分）等操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> fa(n + 1), dep(n + 1);  
vector<i64> dis(n + 1);  
vector<int> dfn, d1(n + 1), d2(n + 1);  
auto dfs = [&](auto &&self, int u) -> void {  
    d1[u] = dfn.size(), d2[u] = dfn.size(), dfn.push_back(u);  
    for (auto [v, w]: adj[u]) {  
        if (v == fa[u]) continue;  
        fa[v] = u;  
        dep[v] = dep[u] + 1;  
        dis[v] = dis[u] + w;  
        self(self, v);  
        d2[u] = dfn.size(), dfn.push_back(u);  
    }  
};  
dfs(dfs, r);

动态维护树的直径

注意到 $dis(u,v)=dep[u]+dep[v]−2dep[lca(u,v)]$ ，使用欧拉序 + 线段树维护树的直径，维护 L-M-R 的组合最值即可，单次操作时间复杂度 $O(logn)$ 。

  • $w$ 为区间深度最大值 。
  • $m$ 为负二倍区间深度最小值，即 $−2dep[lca]$ 。
  • $lm$ 与 $mr$ 分别为 $dep[l]−2dep[lca]$ 和 $dep[r]−2dep[lca]$ 最大值。
  • $lmr$ 为 $dis(l,r)=dep[l]+dep[r]−2dep[lca(l,r)]$ 的最大值，即树的直径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct Tag {  
    i64 val;  
  
    void apply(const Tag &t, int l, int r) {  
        val += t.val;  
    }  
};  
  
struct Info {  
    int valid = 0;  
    i64 w, m, lm, mr, lmr;  
  
    void apply(const Tag &t, int l, int r) {  
        w += t.val;  
        m -= 2 * t.val;  
        lm -= t.val;  
        mr -= t.val;  
    }  
  
    static Info merge(const Info &a, const Info &b) {  
        if (!a.valid) return b;  
        if (!b.valid) return a;  
        return {  
            1,  
            max(a.w, b.w),  
            max(a.m, b.m),  
            max({a.lm, b.lm, a.w + b.m}),  
            max({a.mr, b.mr, a.m + b.w}),  
            max({a.lmr, b.lmr, a.lm + b.w, a.w + b.mr})  
        };  
    }  
};

auto &[u, v, w] = edges[d];  
if (dep[u] < dep[v]) swap(u, v);  
seg.apply(1, 0, dfn.size(), d1[u], d2[u] + 1, {e - w});  
w = e;  

auto info = seg.query(1, 0, dfn.size(), 0, dfn.size());

重链剖分

重链剖分可以将树上的任意一条路径划分成不超过 $O(\log n)$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。

定义子结点中子树大小最大的子结点为重子结点，其余为轻子节点，则可以将树分为若干个由轻子节点开始一直连向重子节点的重链，且树上每个节点都属于且仅属于一条重链。

最后树的 DFS 序上，重链和一颗子树内内的 DFS 序是连续的。按 DFN 排序后的序列即为剖分后的链。

  • fa(x) 表示节点 x 在树上的父亲。
  • dep(x) 表示节点 x 在树上的深度。
  • sz(x) 表示节点 x 的子树的节点个数。
  • son(x) 表示节点 x 的 重儿子。
  • top(x) 表示节点 x 所在 重链 的顶部节点（深度最小）。
  • btn(x) 表示以节点 x 为根节点的子树 DFS 序最靠后的一个节点。
  • dfn(x) 表示节点 x 的 DFS 序，也是其在线段树中的编号。
  • rnk(x) 表示 DFS 序所对应的节点编号，有 rnk(dfn(x))=x。

可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。因此，从 LCA 向下走，树上的每条路径都可以被拆分成不超过 $O(\log{n})$ 条重链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> fa(n + 1), dep(n + 1), sz(n + 1), son(n + 1);  
auto dfs1 = [&](auto &&self, int u) -> int {  
    son[u] = 0, sz[u] = 1;  
    for (auto [v, w]: adj[u]) {  
        if (v == fa[u]) continue;  
        fa[v] = u, dep[v] = dep[u] + 1;  
        sz[u] += self(self, v);  
        if (sz[v] > sz[son[u]]) son[u] = v;  
    }  
    return sz[u];  
};  
dfs1(dfs1, r);  
  
int id = 0;  
vector<int> top(n + 1), btn(n + 1), dfn(n + 1), rnk(n + 1);  
auto dfs2 = [&](auto &&self, int u, int t) -> int {  
    top[u] = t, id++;  
    dfn[u] = id, rnk[id] = u;  
    if (!son[u]) return btn[u] = u;  
    btn[u] = self(self, son[u], t);  
    for (auto [v, w]: adj[u]) {  
        if (v == fa[u] || v == son[u]) continue;  
        btn[u] = self(self, v, v);  
    }  
    return btn[u];  
};  
dfs2(dfs2, r, r);

重链剖分求 LCA

每次选择深度更深的节点向上跳到最近的重链，直到两个节点处于同一条重链，时间复杂度为常数较小的 $O(log{n})$ 。

1
2
3
4
5
6
7
auto lca = [&](int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
};

重链剖分维护路径信息

树链剖分可以将路径拆分序列上 $O(\log{n})$ 段区间，配合线段树、树状数组等维护序列的数据结构，可以维护树上两点路径上的信息，子树上的信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<Info> val(n + 1);  
for (int i = 1; i <= n; ++i) val[dfn[i]].val = nd[i];  
SegmentTree<Info, Tag> seg(val);  
  
auto path_apply = [&](int u, int v, i64 w) {  
    while (top[u] != top[v]) {  
        if (dep[top[u]] < dep[top[v]]) swap(u, v);  
        seg.apply(1, 0, n + 1, dfn[top[u]], dfn[u] + 1, {w});  
        u = fa[top[u]];  
    }  
    if (dep[u] < dep[v]) swap(u, v);  
    seg.apply(1, 0, n + 1, dfn[v], dfn[u] + 1, {w});  
};  
  
auto path_query = [&](int u, int v) {  
    i64 res = 0;  
    while (top[u] != top[v]) {  
        if (dep[top[u]] < dep[top[v]]) swap(u, v);  
        res += seg.query(1, 0, n + 1, dfn[top[u]], dfn[u] + 1).val;  
        u = fa[top[u]];  
    }  
    if (dep[u] < dep[v]) swap(u, v);  
    res += seg.query(1, 0, n + 1, dfn[v], dfn[u] + 1).val;  
    return res % p;  
};

树上启发式合并

对树执行重链剖分后，可以用启发式合并的思想解决一些与每个子树有关的树上离线问题。

遍历到一个节点 $u$ 时，我们按以下的步骤进行遍历：

  1. 先遍历 $u$ 的轻儿子，并计算答案，但 不保留遍历后它对数据结构的影响 ；
  2. 遍历它的重儿子，保留它对数据结构的影响；
  3. 再次遍历 $u$ 的轻儿子的子树结点，加入这些结点的贡献，以得到 $u$ 的答案。

每个节点只会被其祖先中的每个轻节点加入和删除一次，由重链剖分的性质不难得到每个节点的操作次数是 $O(n\log{n})$ 的。注意第一步和第三步不能合并，即不能同时维护多个节点的信息，否则空间不可接受。

以下代码实现了一个通用的树上启发式合并模板，需要先对树执行重链剖分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> ans(n + 1);  
auto dsu = [&](auto &&self, int u, bool keep) -> void {  
    for (int v: adj[u]) {  
        if (v == fa[u] || v == son[u]) continue;  
        self(self, v, false);  
    }  
    if (son[u]) self(self, son[u], true);  
    for (int v: adj[u]) {  
        if (v == fa[u] || v == son[u]) continue;  
        for (int i = dfn[v]; i <= dfn[btn[v]]; i++) {  
            add(rnk[i], 1);  
        }  
    }  
    add(u, 1);  
    ans[u] = cal();  
    if (!keep) {  
        for (int i = dfn[u]; i <= dfn[btn[u]]; i++) {  
            add(rnk[i], -1);  
        }  
    }  
};  
dsu(dsu, 1, false);

长链剖分

长链剖分定义重子节点为子结点中子树深度最大的结点，实现方式和重链剖分类似，仅有数组 sz 的转移不同。

长链剖分从一个结点到根的路径的重链切换次数是 $O(\sqrt{n})$ 级别的。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> fa(n + 1), dep(n + 1), sz(n + 1), son(n + 1);  
auto dfs1 = [&](auto &&self, int u) -> int {  
    son[u] = 0, sz[u] = 1;  
    for (auto [v, w]: adj[u]) {  
        if (v == fa[u]) continue;  
        fa[v] = u, dep[v] = dep[u] + 1;  
        sz[u] = max(sz[u], self(self, v) + 1);  
        if (sz[v] > sz[son[u]]) son[u] = v;  
    }  
    return sz[u];  
};  
dfs1(dfs1, r);

长链剖分优化 DP

当 DP 有一维状态为深度维（注意不带边权）时，我们可以考虑使用长链剖分优化树上 DP 。

每个节点继承其重子节点的 DP 数组，其余子节点的 DP 数组暴力遍历并合并，每个长链的 DP 数组仅在其轻节点被合并一次，因此时间复杂度为 $O(n)$ 。

以下代码实现了长链剖分优化树上求距离恰好为 $k$ 的点对个数，时间复杂度为 $O(qn)$ ，$q$ 为查询次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<int> p(n + 1), dp;  
auto dfs3 = [&](auto &&self, int u) -> void {  
    dp[p[u]] = 1;  
    if (son[u]) {  
        p[son[u]] = p[u] + 1;  
        self(self, son[u]);  
        for (auto &[k, a]: qry) {  
            if (k >= sz[u]) continue;  
            a += dp[p[u] + k];  
        }  
    }  
    for (auto [v, w]: adj[u]) {  
        if (v == fa[u] || v == son[u]) continue;  
        p[son[u]] = dp.size();  
        dp.resize(dp.size() + sz[v]);  
        self(self, v);  
        for (int i = 1; i <= sz[v]; i++) {  
            for (auto &[k, a]: qry) {  
                int r = k - i;  
                if (r < 0 || r >= sz[u]) continue;  
                a += dp[p[u] + r];  
            }  
            dp[p[u] + i] += dp[p[v] + i - 1];  
        }  
    }  
};  
p[1] = dp.size();  
dp.resize(dp.size() + sz[1]);  
dfs3(dfs3, 1);

图的匹配

图的匹配是指在图中选择一组边，使得没有两个边共享同一个节点。

定义如下两种（简单）路径：

  • 交错路：由匹配边与非匹配边交错而成的路径；
  • 增广路：始于未匹配点且终于未匹配点的交错路。

寻找增广路并反转它可以增加匹配大小，这个过程称为 增广 。

Berge 引理说明，当找不到增广路时，就说明已经得到了最大匹配。

二分图最大匹配

Kuhn 算法是匈牙利算法的一部分，从左部的未匹配点出发执行 DFS 找到增广路进行增广。

以下代码实现了充分优化的 Kuhn 算法，利用时间戳优化 vis 数组清空，并在一轮中为多个未匹配点增广，总的轮数 $k$ 不会超过 $|M| + 1$ ，其中 $M$ 为最大匹配。

时间复杂度为 $O(km)$ ，其中 $m$ 为边数。为了避免个别数据将它卡到最差复杂度，在匹配前随机打乱了边的顺序。

注意 $v = adj[u][i]$ 代表左部点 $u$ 向 右部点 $v$ 连有边，左部点和右部点共享编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> ml(n + 1), mr(m + 1), vis(m + 1);  
auto dfs = [&](auto &&self, int u, int t) -> bool {  
    for (int v: adj[u]) {  
        if (vis[v] == t) continue;  
        vis[v] = t;  
        if (!mr[v] || self(self, mr[v], t)) {  
            ml[u] = v, mr[v] = u;  
            return true;  
        }  
    }  
    return false;  
};  
for (int u = 1; u <= n; u++) {  
    shuffle(adj[u].begin(), adj[u].end(), rnd);  
}  
int ans = 0;  
while (true) {  
    int lans = ans;  
    for (int u = 1; u <= n; u++) {  
        if (ml[u]) continue;  
        ans += dfs(dfs, u, lans + 1);  
    }  
    if (ans == lans) break;  
}

二分图最小点覆盖

最小点覆盖问题是指，在一张无向图中选择最少的顶点，满足每条边至少有一个端点被选。

一般图的最小点覆盖问题是 NP-Hard 的，但是对于二分图，Kőnig 定理说明它可以归约为最大匹配问题，同时也给出了最小点覆盖的构造。

设图 $G = (X, Y, E)$ 的一个最大匹配为 $M$。设图 $G$ 中可以由未匹配的左部点 $V$ 出发，沿着某条交错路到达的顶点集合为 $Z$。于是，顶点集合 $C = (X \setminus Z) \cup (Y \cap Z)$ 就是所求的最小点覆盖。

从网络流的角度看，最小点覆盖问题就是最小割问题：选择左部点，相当于切割它与源点的连边；选择右部点，相当于切割它与汇点的连边。

从线性规划的角度看，最小点覆盖问题就是最大匹配问题的对偶问题。因此，König 定理可以看作是最大流最小割定理的特殊情形，或者更一般地，线性规划的强对偶定理的特殊情形。

二分图最大独立集

最大独立集问题是指，在一张无向图中选择最多的顶点，满足两两之间互不相邻。

对于一般图 $G = (V, E)$ ，点集 $C \subseteq V$ 是点覆盖，当且仅当它的补集 $V \setminus C$ 是独立集。

因此，与最小点覆盖问题一样，最大独立集问题对于一般图是 NP-Hard 的，但是对于二分图它可以归约为最大匹配问题求解。

二分图最大权匹配

二分图的最大权匹配是指二分图边权和最大的匹配，有时还要求完美匹配，即二分图最大权完美匹配。

Kuhn–Munkrese 算法

Kuhn–Munkrese 算法可以在 $O(n^3)$ 的时间复杂度内求出二分图最大权完美匹配。

KM 算法复杂度与边无关，如果两点没有连边的话，可以假设这两点的边的权值为 $0$ 以求出最大权匹配，或设为 $-inf$ 以求出最大权完美匹配。

如果二分图中两个集合中的点个数不同，需要先将两个集合中点数比较少的加上虚点，使得两边点数相同，然后将原本不存在的边连成虚边。

对于需要特判无解的题目，我们需要极力避免选择虚边，也就是将虚边边权设为 $−inf$，如果被迫选了 $−inf$ 的边就输出无解。

对于允许非完美匹配的题目，我们允许选取虚边，也就是将虚边边权设为 $0$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int n, m;  
cin >> n >> m;  
vector g(n + 1, vector(n + 1, -infl));  
for (int i = 0; i < m; i++) {  
    int y, c;  
    i64 h;  
    cin >> y >> c >> h;  
    if (h > g[y][c]) g[y][c] = h;  
}  
  
vector<i64> lx(n + 1), ly(n + 1), slack(n + 1);  
vector<int> prev(n + 1), match(n + 1), vis(n + 1);  
for (int i = 1; i <= n; i++) {  
    lx[i] = -infl;  
    for (int j = 1; j <= n; j++) {  
        if (g[i][j] > lx[i]) lx[i] = g[i][j];  
    }  
}  
  
for (int i = 1; i <= n; i++) {  
    fill(slack.begin() + 1, slack.end(), infl);  
    int j0 = 0;  
    match[0] = i;  
    while (true) {  
        vis[j0] = i;  
        int u = match[j0], j1 = 0;  
        i64 d = infl;  
        for (int j = 1; j <= n; j++) {  
            if (vis[j] == i) continue;  
            i64 tmp = lx[u] + ly[j] - g[u][j];  
            if (tmp < slack[j]) {  
                slack[j] = tmp;  
                prev[j] = j0;  
            }  
            if (slack[j] < d) {  
                d = slack[j];  
                j1 = j;  
            }  
        }  
        for (int j = 0; j <= n; j++) {  
            if (vis[j] == i) {  
                lx[match[j]] -= d;  
                ly[j] += d;  
            } else {  
                slack[j] -= d;  
            }  
        }  
        j0 = j1;  
        if (match[j0] == 0) break;  
    }  
    while (j0) {  
        match[j0] = match[prev[j0]];  
        j0 = prev[j0];  
    }  
}  
  
i64 ans = 0;  
for (int i = 1; i <= n; i++) {  
    ans += g[match[i]][i];  
}  
  
cout << ans << '\n';  
for (int i = 1; i <= n; i++) {  
    cout << match[i] << " \n"[i == n];  
}

转化为网络流

对于二分图的最大权匹配问题，可以将其转化为网络流问题来求解。具体步骤如下：

首先，在图中新增一个源点 $s$ 和一个汇点 $t$ 。

从源点 $s$ 向二分图的每个左部点连一条流量为 $1$、费用为 $0$ 的边；从二分图的每个右部点向汇点 $t$ 连一条流量为 $1$、费用为 $0$ 的边 。

接下来，对于二分图中每一条连接左部点 $u$ 和右部点 $v$、边权为 $w$ 的边，则连一条从 $u$ 到 $v$ 的边，流量为 $1$，费用为 $w$ 。

另外，考虑到最大权匹配下，匹配边的数量不一定与最大匹配的匹配边数量相等，因此对于每个左部点，还需向汇点 $t$ 连一条流量为 $1$、费用为 $0$ 的边（如果不要求完美匹配，即要求匹配边数量最大，则不需要这样做）。

求这个网络的最大费用最大流即可得到答案。此时，该网络的最大流量一定为左部点的数量，而最大流量下的最大费用即对应一个最大权匹配方案。

网络流

网络指一个特殊的有向图其，有容量和源汇点。流是从边到数的映射，满足容量限制和每个点的流量守恒。

建模方法

将问题抽象为带容量的有向图，定义源点和汇点，将约束转化为边的容量，将目标转化为求最大流/最小割/最小费用流。核心是设计图的连接方式。

多源多汇建模

这类问题存在多个源点 $s{i}$ 和汇点 $t{i}$ ，还存在流量限制 $w_{i}$​ 。

增加超级汇 $s$ 和超级汇 $t$，从 $s$ 向每个 $s{i}$​ 连容量为 $w{i}$​ 的边，从每个 $t{i}$ 向 $t$ 连容量为 $w{i}$​ 的边，即可转化为源单汇问题。

二分图最大匹配问题可以使用多源多汇建模解决，即将左部点视为流量限制为为 $1$ 的源点，右部点视为流量限制为为 $1$ 的汇点，求最大总流量。

路径覆盖与链覆盖

DAG 的最小路径覆盖的定义就是每次可以从任意点出发，用尽可能少的不相交的路径覆盖掉整张 DAG 。

考虑将每个结点看做一个路径，每个相邻结点可以合并，此时路径长度就会减少，因此我们应该最大化可合并的相邻结点的个数。

将每个点 $u$ 拆成 $u’$ 和 $u’’$，分别为左部点和右部点。每次处理形如 $u \to v$ 的连边就将 $u’$ 连向 $v’’$，即转化为二分图最大匹配问题，用总点数减去最大匹配数，就是最小路径覆盖总数。

输出方案可以用从所有起点（即入度为 $0$ 的点）开始递归遍历出边对应结点的 X 部分的结点。

如果路径可以相交，则变为 DAG 的最小链覆盖问题，使用 Floyd 算法对原图求出传递闭包，求出原图的传递闭包后，直接在传递闭包上跑最小路径覆盖即可。

最大流最小割定理

对于任意网络，其最大流等于最小割。

可以从最小割的角度考虑问题进行建模，即割去某些边表示计算或减去贡献，用 $inf$ 容量的边确保两个点划分到同一侧。

拆点法

将一个结点 $u$ 拆分为 $u’$ 和 $u’’$，所有到达 $u$ 的边 $v \to u$ 都转化为连向 $u’$ 的边，所有从 $u$ 出去的边 $u \to v$ 都转化为从 $u’’$ 出去的边，然后可以从 $u’$ 向 $u’’$ 连一条容量为 $k$ 的边用于限制 $u$ 的流量。

对于更复杂的问题，可以考虑将点按某些关系拆成更多点，以设计更复杂的连边。

染色法

给定网络图，要求取出一些结点，使得贡献最大，要求被取的结点不能相邻。

考虑用总贡献减去最小不取方格的贡献，并将原网格图黑白染色。源点连向黑点，白点连向汇点，容量为对应点的贡献，不能相邻的黑白点对连容量为 $inf$ 的边表示至少割掉其中一个，每个割均能表示不取某些方格后合法的方案，即转化为求最小割。

除了黑白染色，还存在行/列奇偶性染色等不同染色法。对于这类给定冲突点对的问题，都可以考虑染色，令同颜色集合内没有冲突点对，即可转化为二分图最小割问题。

划分问题

全班分科，每位同学分到文科能获得一定满意值，分到理科能获得一定满意值，如果上下左右的同学都被分到同一科也能增加一定的满意值，要求找到最优划分，使得满意值最大。

考虑用总贡献减去无法取得的贡献，将源点连向当前结点，容量为选文科的贡献，当前结点连向汇点，容量为选理科得到的贡献，如果其中有一条边被割了，就说明不选该科，转化为求最小割。

对于某个要求同为文科的贡献，可以建立虚点，源点连向该虚点，容量为贡献，虚点连向必须同时选文科的点，容量为 $inf$ ，即存在理科边未割时需要被删去该贡献。

s-t 平面图最小割

图中的一个点为源点 $s$ ，另外一个点为汇点 $t$ ，且 $s$ 和 $t$ 都在图中的无界面的边界上，这种图称为 s-t 平面图。

将每个平面视为点，存在公共边的平面连边，边权为公共边边权，可以得到对偶图。

s-t 平面图最小割可以转化为对偶图中的最短路。

上下界网络流建模

上下界网络流本质是给定覆盖网络的每一条边设置了流量上界 $c(u,v)$ 和流量下界 $b(u,v)$。也就是说，一种可行的流必须满足 $b(u,v) \leq f(u,v) \leq c(u,v)$，同时必须满足除了源点和汇点之外的其余点流量平衡。

无源汇上下界可行流

给定无源汇流量网络 $G_0$，询问是否存在一种特定每条边流量的方式，使得每条边流量满足上下界同时每一个点流量平衡。

不妨假设每条边已经流了 $b(u,v)$ 的流量，设其为初始流。同时我们在新图中加入 $u$ 连向 $v$ 的流量为 $c(u,v) - b(u,v)$ 的边。考虑在新的图上进行调整。

由于最大流需要满足初始流量平衡条件（最大流可以看成是下界为 $0$ 的上界最大流），但是构造出来的初始流很有可能不满足初始流量平衡。假设一个点初始流入流量被初始流出流量为 $M$。

若 $M = 0$，此时流量平衡，不需要附加边。

若 $M > 0$，此时入流量过大，需要新建附加源点 $S’$，$S’$ 向其连流量为 $M$ 的附加边。

若 $M < 0$，此时出流量过大，需要新建附加汇点 $T’$，其向 $T’$ 连流量为 $M$ 的附加边。

原图加上附加流之后才会满足原图中的流量平衡，如果附加边满流，说明这个点的流量平衡条件可以满足，否则这个点的流量平衡条件不满足。

在建立完毕之后把 $S’$ 到 $T’$ 的最大流，若 $S’$ 连出去的边全部满流，则存在可行流，否则不存在。

有源汇上下界可行流

给定有源汇流量网络 $G_0$，询问是否存在一种特定每条边流量的方式，使得每条边流量满足上下界同时每个点流量平衡。

假设源点为 $S$，汇点为 $T$。

则我们可以加入一条 $T$ 到 $S$ 的上界为 $\infty$，下界为 $0$ 的边转化为无源汇上下界可行流问题。

若有解，则 $S$ 到 $T$ 的可行流流量等于 $T$ 到 $S$ 的附加边的流量。

有源汇上下界最大/最小流

给定有源汇流量网络 $G_0$，询问是否存在一种特定每条边流量的方式，使得每条边流量满足上下界同时每个点流量平衡。如果存在，询问满足特定的最大/最小流量。

我们找到网络上的任意一个可行流，如果找不到解就可以直接结束，否则考虑删去所有附加边之后的残量网络并且在网络上进行调整。

否则我们考虑删去所有附加边之后的残量网络并且在网络上进行调整。

在残量网络上再跑一次 $S$ 到 $T$ 的最大流，将可行流流量和最大流流量相加即为有源汇上下界最大流。

同样地，在残量网络上再跑一次 $T$ 到 $S$ 的最大流，将可行流流量和最大流流量相减即为有源汇上下界最小流。

网络最大流算法

令 $G=(V,E)$ 是一个有源汇点的网络，我们希望在 $G$ 上指定合适的流 $f$，以最大化整个网络的流量 $|f|$ （即 $\sum{x \in V} f(s, x) - \sum{x \in V} f(x, s)$），这一问题被称作最大流问题。

以下算法建图方法均为：

1
2
3
4
struct edge {  
    int v, r;  
    i64 w, f;  
};

Dinic 算法

Dinic 算法是一种用于解决最大流问题的高效算法，通过分层图和分层深度优先搜索增广流量，优化了增广路径的寻找过程，最坏复杂度 $O(n^{2}m)$ ，但在在一些性质良好的图上，Dinic 算法有更好的时间复杂度。

稠密图 稀疏图 平面图 二分图 有向无环图 单位容量网络
$O(n^{2}m)$ $O(n^{\frac{3}{2}})$ $O(n^{\frac{3}{2}})$ $O(\sqrt{n}m)$ $O(nm)$ $O(m \min(m^\frac{1}{2}, n^{\frac{2}{3}}))$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
struct Flow {  
    vector<vector<edge> > adj;  
    vector<int> dep, cur;  
  
    explicit Flow(int n) : adj(n), dep(n, -1), cur(n) {  
    }  
  
    void add_edge(int u, int v, i64 w) {  
        adj[u].emplace_back(v, (int) adj[v].size(), w, 0);  
        adj[v].emplace_back(u, (int) adj[u].size() - 1, 0, 0);  
    }  
  
    bool bfs(int s, int t) {  
        ranges::fill(dep, -1);  
        queue<int> q;  
        q.push(s);  
        dep[s] = 0;  
        while (!q.empty()) {  
            int u = q.front();  
            q.pop();  
            for (auto &[v, r, w, f]: adj[u]) {  
                if (~dep[v] || w <= f) continue;  
                dep[v] = dep[u] + 1;  
                if (v == t) return true;  
                q.push(v);  
            }  
        }  
        return false;  
    }  
  
    i64 dfs(int u, int t, i64 flow) {  
        if (u == t) return flow;  
        i64 res = 0;  
        for (int &i = cur[u]; i < adj[u].size(); i++) {  
            auto &[v, r, w, f] = adj[u][i];  
            if (dep[v] != dep[u] + 1 || w <= f) continue;  
            i64 d = dfs(v, t, min(flow - res, w - f));  
            if (d <= 0) continue;  
            res += d, f += d;  
            adj[v][r].f -= d;  
            if (res == flow) return res;  
        }  
        return res;  
    }  
  
    i64 dinic(int s, int t) {  
        i64 res = 0;  
        while (bfs(s, t)) {  
            ranges::fill(cur, 0);  
            res += dfs(s, t, infl);  
        }  
        return res;  
    }  
};

ISAP 算法

ISAP 算法是 Dinic 算法的优化版本，通过反向 BFS 初始化分层，并在增广的过程中完成重分层，从而避免多次运行 BFS 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct Flow {  
    int n;  
    vector<vector<edge> > adj;  
    vector<int> dep, cur, gap;  
  
    explicit Flow(int n) : n(n), adj(n), dep(n, -1), cur(n), gap(n + 2) {  
    }  
  
    void add_edge(int u, int v, i64 w) {  
        adj[u].emplace_back(v, (int) adj[v].size(), w, 0);  
        adj[v].emplace_back(u, (int) adj[u].size() - 1, 0, 0);  
    }  
  
    void init(int t) {  
        queue<int> q;  
        q.push(t);  
        dep[t] = 0;  
        while (!q.empty()) {  
            int u = q.front();  
            q.pop();  
            for (auto &[v, r, w, f]: adj[u]) {  
                if (~dep[v] || adj[v][r].w <= adj[v][r].f) continue;  
                dep[v] = dep[u] + 1;  
                q.push(v);  
            }  
        }  
    }  
  
    i64 dfs(int u, int s, int t, i64 flow) {  
        if (u == t) return flow;  
        i64 res = 0;  
        for (int &i = cur[u]; i < adj[u].size(); i++) {  
            auto &[v, r, w, f] = adj[u][i];  
            if (dep[v] + 1 != dep[u] || w <= f) continue;  
            i64 d = dfs(v, s, t, min(flow - res, w - f));  
            if (d <= 0) continue;  
            res += d, f += d;  
            adj[v][r].f -= d;  
            if (res == flow) return res;  
        }  
        if (--gap[dep[u]] == 0) dep[s] = n;  
        ++gap[++dep[u]], cur[u] = 0;  
        return res;  
    }  
  
    i64 isap(int s, int t) {  
        init(t);  
        if (dep[s] == -1) return 0;  
        for (int u = 0; u < n; ++u) {  
            if (~dep[u]) gap[dep[u]]++;  
        }  
        i64 res = 0;  
        while (dep[s] < n) res += dfs(s, s, t, infl);  
        return res;  
    }  
};

容量缩放算法

容量缩放优化的 Dinic 算法，时间复杂度 $O(nm\log{U})$，其中 $U$ 为所有边的最大容量。$\log{U}$ 部分上界较紧，正常情况不建议使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct Flow {  
    vector<vector<edge> > adj;  
    vector<int> dep, cur;  
  
    explicit Flow(int n) : adj(n), dep(n, -1), cur(n) {  
    }  
  
    void add_edge(int u, int v, i64 w) {  
        adj[u].emplace_back(v, (int) adj[v].size(), w, 0);  
        adj[v].emplace_back(u, (int) adj[u].size() - 1, 0, 0);  
    }  
  
    bool bfs(int s, int t, i64 dt) {  
        ranges::fill(dep, -1);  
        queue<int> q;  
        dep[s] = 0, q.push(s);  
        while (!q.empty()) {  
            int u = q.front();  
            q.pop();  
            for (auto &[v, r, w, f]: adj[u]) {  
                if (~dep[v] || w - f < dt) continue;  
                dep[v] = dep[u] + 1;  
                if (v == t) return true;  
                q.push(v);  
            }  
        }  
        return false;  
    }  
  
    i64 dfs(int u, int t, i64 flow, i64 dt) {  
        if (u == t) return flow;  
        i64 res = 0;  
        for (int &i = cur[u]; i < adj[u].size(); ++i) {  
            auto &[v, r, w, f] = adj[u][i];  
            if (dep[v] != dep[u] + 1 || w - f < dt) continue;  
            i64 d = dfs(v, t, min(flow - res, w - f), dt);  
            if (d <= 0) continue;  
            res += d, f += d;  
            adj[v][r].f -= d;  
            if (res == flow) return res;  
        }  
        return res;  
    }  
  
    i64 scdinic(int s, int t) {  
        i64 res = 0;  
        for (i64 dt = 1ll << 31; dt > 0; dt >>= 1) {  
            while (bfs(s, t, dt)) {  
                ranges::fill(cur, 0);  
                res += dfs(s, t, infl, dt);  
            }  
        }  
        return res;  
    }  
};

HLPP 算法

在通用的预流推送算法基础上，优先选择高度最高的溢出结点推送，算法复杂度为 $O(n^2\sqrt{m})$。

包含 BFS 优化和 GAP 优化，只处理高度小于 $n$ 的溢出节点，如需获得每条边的流量需处理高度小于 $2\times{n}$ 的溢出节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
constexpr int inf = 1e9;  
  
struct Flow {  
    int n, mh;  
    vector<vector<int> > bk;  
    vector<vector<edge> > adj;  
    vector<int> ht, gap;  
    vector<i64> ex;  
  
    explicit Flow(int n) : n(n), mh(0), bk(n), adj(n), ht(n, inf), gap(n), ex(n) {  
    }  
  
    void add_edge(int u, int v, i64 w) {  
        adj[u].emplace_back(v, (int) adj[v].size(), w, 0);  
        adj[v].emplace_back(u, (int) adj[u].size() - 1, 0, 0);  
    }  
  
    int top() {  
        while (~mh && bk[mh].empty()) mh--;  
        return mh == -1 ? 0 : bk[mh].back();  
    }  
  
    bool push(int u, int s, int t) {  
        bool init = u == s;  
        for (auto &[v, r, w, f]: adj[u]) {  
            if (w <= f || ht[v] == inf || !init && ht[u] != ht[v] + 1) continue;  
            if (v != s && v != t && !ex[v]) {  
                bk[ht[v]].push_back(v);  
                mh = max(mh, ht[v]);  
            }  
            i64 d = init ? w : min(ex[u], w - f);  
            f += d, adj[v][r].f -= d, ex[u] -= d, ex[v] += d;  
            if (!ex[u]) return false;  
        }  
        return true;  
    }  
  
    void relabel(int u) {  
        ht[u] = inf;  
        for (auto &[v, r, w, f]: adj[u]) {  
            if (w > f) ht[u] = min(ht[u], ht[v] + 1);  
        }  
        if (ht[u] < n) {  
            bk[ht[u]].push_back(u);  
            mh = max(mh, ht[u]);  
            ++gap[ht[u]];  
        }  
    }  
  
    bool bfs(int s, int t) {  
        queue<int> q;  
        q.push(t);  
        ht[t] = 0;  
        while (!q.empty()) {  
            int u = q.front();  
            q.pop();  
            for (auto &[v, r, w, f]: adj[u]) {  
                if (w || ht[v] <= ht[u] + 1) continue;  
                ht[v] = ht[u] + 1;  
                q.push(v);  
            }  
        }  
        return ht[s] != inf;  
    }  
  
    i64 hlpp(int s, int t) {  
        if (!bfs(s, t)) return 0;  
        for (auto h: ht) {  
            if (h != inf) gap[h]++;  
        }  
        ht[s] = n;  
  
        int u;  
        push(s, s, t);  
        while ((u = top())) {  
            bk[mh].pop_back();  
            if (!push(u, s, t)) continue;  
            if (!--gap[ht[u]]) {  
                for (int i = 0; i < n; i++) {  
                    if (i != s && i != t && ht[i] > ht[u] && ht[i] < n + 1) {  
                        ht[i] = n + 1;  
                    }  
                }  
            }  
            relabel(u);  
        }  
        return ex[t];  
    }  
};

最小费用最大流

最小费用最大流是指在网络流中找到一个流量最大的可行流，同时满足总费用最小的优化问题。

以下模板建图方法均为：

1
2
3
4
struct edge {  
    int v, r;  
    i64 w, f, c;  
};

SSP-EK 算法

以下代码是一个基于 EK 算法的 SSP 最小费用最大流实现，使用 SPFA 算法寻找增广路径，时间复杂度为 $O(nmf)$，其中 $f$ 是最大流量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct Flow {  
    vector<vector<edge> > adj;  
    vector<int> pn, pe;  
    vector<i64> dis;  
    i64 cost;  
  
    explicit Flow(int n) : adj(n), pn(n), pe(n), dis(n), cost(0) {  
    }  
  
    void add_edge(int u, int v, i64 w, i64 c) {  
        adj[u].emplace_back(v, (int) adj[v].size(), w, 0, c);  
        adj[v].emplace_back(u, (int) adj[u].size() - 1, 0, 0, -c);  
    }  
  
    bool spfa(int s, int t) {  
        ranges::fill(dis, infl);  
        queue<int> q;  
        dis[s] = 0, pn[t] = -1, q.push(s);  
        while (!q.empty()) {  
            int u = q.front();  
            q.pop();  
            for (int i = 0; i < adj[u].size(); i++) {  
                auto &[v, r, w, f, c] = adj[u][i];  
                if (w > f && dis[v] > dis[u] + c) {  
                    dis[v] = dis[u] + c;  
                    pn[v] = u, pe[v] = i;  
                    q.push(v);  
                }  
            }  
        }  
        return pn[t] != -1;  
    }  
  
    i64 ssp(int s, int t) {  
        i64 res = 0;  
        cost = 0;  
        while (spfa(s, t)) {  
            i64 d = infl;  
            for (int v = t; v != s; v = pn[v]) {  
                int u = pn[v], i = pe[v];  
                d = min(d, adj[u][i].w - adj[u][i].f);  
            }  
            for (int v = t; v != s; v = pn[v]) {  
                int u = pn[v], i = pe[v];  
                adj[u][i].f += d;  
                adj[adj[u][i].v][adj[u][i].r].f -= d;  
            }  
            res += d;  
            cost += d * dis[t];  
        }  
        return res;  
    }  
};

SSP-zkw 算法

反向求最短路，多路增广优化，时间复杂度仍为 $O(nmf)$，但在大多数图，尤其是层次小，流量大，费用小的图更具优势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Flow {  
    vector<vector<edge> > adj;  
    vector<char> vis;  
    vector<i64> dis;  
    i64 cost;  
  
    explicit Flow(int n) : adj(n), vis(n), dis(n), cost(0) {  
    }  
  
    void add_edge(int u, int v, i64 w, i64 c) {  
        adj[u].emplace_back(v, (int) adj[v].size(), w, 0, c);  
        adj[v].emplace_back(u, (int) adj[u].size() - 1, 0, 0, -c);  
    }  
  
    bool spfa(int s, int t) {  
        ranges::fill(vis, false);  
        ranges::fill(dis, infl);  
        queue<int> q;  
        dis[t] = 0, vis[t] = true, q.push(t);  
        while (!q.empty()) {  
            int u = q.front();  
            vis[u] = false, q.pop();  
            for (auto &[v, r, w, f, c]: adj[u]) {  
                if (adj[v][r].w <= adj[v][r].f || dis[v] <= dis[u] - c) continue;  
                dis[v] = dis[u] - c;  
                if (!vis[v]) vis[v] = true, q.push(v);  
            }  
        }  
        return dis[s] != infl;  
    }  
  
    i64 dfs(int u, int t, i64 flow) {  
        vis[u] = true;  
        if (u == t) return flow;  
        i64 res = 0;  
        for (auto &[v, r, w, f, c]: adj[u]) {  
            if (vis[v] || dis[v] + c != dis[u] || w <= f) continue;  
            i64 d = dfs(v, t, min(flow - res, w - f));  
            if (d <= 0) continue;  
            res += d, f += d;  
            adj[v][r].f -= d;  
            cost += d * c;  
            if (res == flow) return res;  
        }  
        return res;  
    }  
  
    i64 ssp(int s, int t) {  
        i64 res = 0;  
        cost = 0;  
        while (spfa(s, t)) {  
            vis[t] = true;  
            while (vis[t]) {  
                ranges::fill(vis, false);  
                res += dfs(s, t, infl);  
            }  
        }  
        return res;  
    }  
};

Primal-Dual 原始对偶算法

Primal-Dual 原始对偶算法的思路与 Johnson 全源最短路径算法类似，通过为每个点设置一个势能，将网络上所有边的费用全部变为非负值，从而可以应用 Dijkstra 算法找出网络上单位费用最小的增广路。