图论

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

存图方式

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

邻接表

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

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

int main {
    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 <= sc; u++) {  
    if (deg[u]) continue;  
    q.push(u), tfn.push_back(u);  
}  
while (!q.empty()) {  
    int u = q.front();  
    q.pop();  
    for (auto v: cadj[u]) {  
        if (--deg[v]) continue;  
        q.push(v), tfn.push_back(v);  
    }  
}

最短路

Floyd 算法

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

若存在任意节点 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 传递闭包算法通过动态规划逐步枚举中间节点，在 Θ(n3) 时间内计算出有向图中所有点对的可达性。

使用 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
18
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]) {  
                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
18
19
20
21
22
struct node {  
    int u, d;  
};  
  
vector<int> dis(n + 1, inf);  
auto dijkstra = [&](int s) {  
    constexpr auto cmp = [](auto x, auto y) { return x.d > y.d; };  
    priority_queue<node, vector<node>, decltype(cmp)> q(cmp);  
    dis[s] = 0;  
    q.emplace(s, 0);  
    while (!q.empty()) {  
        auto [u, d] = q.top();  
        q.pop();  
        if (dis[u] < d) continue;  
        for (auto [v, w]: adj[u]) {  
            if (dis[u] + w < dis[v]) {  
                dis[v] = dis[u] + w;  
                q.emplace(v, dis[v]);  
            }  
        }  
    }  
};

Johnson 算法

新建一个虚拟节点（设其编号为 0 ）。从这个点向其他所有点连一条边权为 0 的边，然后用 SPFA 求出 0 号点到其它所有点的最短路作为势能函数，然后根据势能函数重新标注边权使边权非负，然后就可以跑 n 轮 Dijkstra 计算最短路，时间复杂度 O(nmlog 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 算法是一种贪心算法，通过按边权从小到大排序并依次选择不构成环的边来构造最小生成树。

以下代码使用并查集判环，Kruskal 部分时间复杂度为 O(mα(n))，总时间复杂度 O(mlog m) 。

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

Prim 算法

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

以下代码使用优先队列实现，时间复杂度为 O((n + m)log m) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct node {  
    int u, d;  
};

auto prim = [&]() {  
    vector<char> vis(n + 1);  
    constexpr auto cmp = [](auto x, auto y) { return x.d > y.d; };  
    priority_queue<node, vector<node>, decltype(cmp)> pq(cmp);  
    pq.emplace(1, 0);  
    int sum = 0, cnt = 0;  
    while (!pq.empty() && cnt < n) {  
        auto [u, d] = pq.top();  
        pq.pop();  
        if (vis[u]) continue;  
        vis[u] = true;  
        sum += d;  
        cnt++;  
        for (auto &[v, w]: adj[u]) {  
            if (vis[v]) continue;  
            pq.emplace(v, w);  
        }  
    }  
    return cnt == n ? sum : -1;  
};

Boruvka 算法

Boruvka 算法通过多轮迭代，每轮为每个连通分量寻找最优边合并连通分量，求解最小生成树。其在稠密图或边具有较多特殊性质的问题中具有优势，时间复杂度为 O(mlog 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
vector<tuple<int, int, int>> edges;  
auto boruvka = [&]() -> int {  
    DSU dsu(n + 1);  
    bool upd = true;  
    int sum = 0, cnt = 0;  
    while (upd) {  
        upd = false;  
        vector<int> id(n + 1, -1);  
        for (int i = 0; i < m; i++) {  
            auto &[u, v, w] = ed[i];  
            int x = dsu.find(u), y = dsu.find(v);  
            if (x == y) continue;  
            if (id[x] == -1 || w < get<2>(ed[id[x]])) id[x] = i;  
            if (id[y] == -1 || w < get<2>(ed[id[y]])) id[y] = i;  
            upd = true;  
        }  
        for (int i = 1; i <= n; i++) {  
            if (id[i] == -1) continue;  
            auto &[u, v, w] = ed[id[i]];  
            id[i] = -1;  
            if (!dsu.merge(u, v)) continue;  
            sum += w, cnt++;  
        }  
    }  
    return cnt == n - 1 ? sum : -1;  
};

连通性相关算法

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

Tarjan 算法

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

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

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

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

割点

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

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

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

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

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), 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;  
};

割边

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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, u);  
            low[u] = min(low[u], low[v]);  
            if (low[v] > dfn[u]) bri[v] = true;  
        } else {  
            low[u] = min(low[u], dfn[v]);  
        }  
    }  
};

边双连通分量

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

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

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

以下实现中，bcc[u] 表示 u 所属的边双连通分量编号，sz[s] 表示边双连通分量 s 的大小，注意每条边上定义了唯一正编号 i 以处理重边。

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
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);  
    }  
};

强连通分量

强连通分量（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 预处理出每个节点第 2i 祖先节点，可求两节点间最近公共祖先 (LCA)。

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

倍增算法的预处理时间复杂度为 O(nlog 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
// 最大深度，视题目范围确定，也可直接取31
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 ），常数更小，实现更简单。

不妨设 dfnu​ < dfnv ​，若 u ≠ v，则它们的 LCA 等于 DFS 序上位置在 (dfnu​, dfnv] 的深度最小的任意结点的父亲。

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

以下为 DFS 序转化为 RMQ 问题求 LCA 的实现，直接在 RMQ 的最底层记录父亲，比较时取 dfn 更小的结点，避免了记录每个结点的父亲 fa 和深度 dep 。预处理时间复杂度 O(n) ，查询期望时间复杂度 O(1) ，依赖于分块 RMQ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int id = 1;  
vector<int> dfn(n + 1, inf), 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);  
  
BlockRMQ rmq(val, 0, [&](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] + 1, dfn[v] + 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。

树链剖分配合线段树、树状数组可以维护树上两点路径上的信息，子树上的信息。

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
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);  
  
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;  
};

图的匹配

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

二分图最大匹配

使用匈牙利算法来进行增广路径搜索，从而寻找最大匹配，时间复杂度为 O(nlnr) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> ml(n + 1), mr(m + 1), vis(m + 1);
auto dfs = [&](auto &&self, int u, int t) -> bool {
    for (int v = 1; v <= m; ++v) {
        if (!adj[u][v]) continue;
        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;
};

int ans = 0;
for (int u = 1; u <= n; ++u) {
    if (ml[u]) continue;
    ans += dfs(dfs, u, u);
}

网络最大流

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

以下算法建图方法均为：

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

Dinic 算法

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

稠密图 稀疏图 平面图 二分图 有向无环图 单位容量网络
O(n2m) $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
55
56
constexpr i64 inf = 1e18;  
  
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, inf);  
        }  
        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(nmlog 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
56
57
constexpr i64 inf = 1e18;  
  
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, inf, dt);  
            }  
        }  
        return res;  
    }  
};

HLPP 算法

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

包含 BFS 优化和 GAP 优化，只处理高度小于 n 的溢出节点，如需获得每条边的流量需处理高度小于 2 × 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
54
55
constexpr i64 inf = 1e18;  
  
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, inf);  
        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 = inf;  
            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
61
62
constexpr i64 inf = 1e18;  

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, inf);  
        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] != inf;  
    }  
  
    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, inf);  
            }  
        }  
        return res;  
    }  
};

Primal-Dual 原始对偶算法

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