A

算法标签: 模拟

题目描述

给定一个由数字组成的字符串 $S$。

请从 $S$ 中删除所有不是 2 的字符，并将剩余字符按原有顺序拼接成新字符串。

输入格式

输入通过标准输入按以下格式给出：

$S$

输出格式

输出答案。

输入输出样例 #1

输入 #1

20250222

输出 #1

22222

输入输出样例 #2

输入 #2

2

输出 #2

2

输入输出样例 #3

输入 #3

22222000111222222

输出 #3

22222222222

说明/提示

约束条件

• $S$ 是由数字组成的长度介于 $1$ 到 $100$ 之间的字符串
• $S$ 至少包含 $1$ 个 2

样例解释 1

从 20250222 中删除 0, 5, 0 后，将剩余字符按原有顺序拼接得到字符串 22222。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string str;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> str;
	string res;
	for (char c : str) {
		if (c == '2') res += c;
	}

	cout << res << "\n";
	return 0;
}

B

算法标签: 模拟

题目描述

给定 $N$ 个由小写字母组成的字符串 $S_1,S_2,\dots ,S_N$，其中所有字符串的长度互不相同。

请将这些字符串按长度升序排列，并按此顺序拼接后输出结果字符串。

输入格式

输入通过标准输入按以下格式给出：

$N$
$S_1$
$S_2$
$⋮$
$S_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3
tc
oder
a

输出 #1

atcoder

输入输出样例 #2

输入 #2

4
cat
enate
on
c

输出 #2

concatenate

说明/提示

约束条件

• $2\le N\le 50$
• $N$ 为整数
• $S_i$ 是长度介于 $1$ 到 $50$ 之间的由小写字母组成的字符串
• 当 $i\ne j$ 时，$S_i$ 和 $S_j$ 的长度不同

样例解释 1

将（tc, oder, a）按字符串长度升序排列后得到（a, tc, oder）。将这些字符串按顺序拼接后得到字符串 atcoder。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<string, int> PSI;

const int N = 50 + 10;

int n;
PSI w[N];

bool cmp(PSI u, PSI v) {
	return u.second < v.second;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		string str;
		cin >> str;
		w[i] = {str, str.size()};
	}
	sort(w, w + n, cmp);

	string res;
	for (int i = 0; i < n; ++i) res += w[i].first;

	cout << res << "\n";
	return 0;
}

C

算法标签: 模拟

题目描述

给定一个仅由大写字母组成的字符串 $S$。
请输出对 $S$ 执行以下操作后得到的最终字符串：

只要字符串中包含连续的 WA 子字符串，就重复执行以下操作：

• 将字符串中首次出现的 WA 替换为 AC。

可以证明在本题的约束条件下，此操作最多只能执行有限次。

输入格式

输入通过标准输入按以下格式给出：

$S$

输出格式

输出对 $S$ 执行题目所述操作后得到的字符串。

输入输出样例 #1

输入 #1

WACWA

输出 #1

ACCAC

输入输出样例 #2

输入 #2

WWA

输出 #2

ACC

输入输出样例 #3

输入 #3

WWWWW

输出 #3

WWWWW

说明/提示

约束条件

• $S$ 是长度介于 $1$ 到 $3\times 10^5$ 之间的仅由大写字母组成的字符串

样例解释 1

初始字符串为 $S=$ WACWA。该字符串包含从第 $1$ 到 $2$ 个字符和从第 $4$ 到 $5$ 个字符的 WA 子字符串。第一次操作将替换最先出现的部分（即第 $1$ 到 $2$ 个字符），得到 ACCWA。此时字符串仅剩第 $4$ 到 $5$ 个字符的 WA，第二次操作替换后得到 ACCAC。由于 ACCAC 不再包含 WA，操作终止，因此输出 ACCAC。

样例解释 2

初始字符串为 $S=$ WWA。该字符串仅在第 $2$ 到 $3$ 个字符处包含 WA。第一次操作替换后得到 WAC，此时新字符串在第 $1$ 到 $2$ 个字符处出现 WA。第二次操作替换后得到 ACC。由于不再包含 WA，操作终止，因此输出 ACC。

样例解释 3

原始字符串 $S$ 中不包含 WA 子字符串，因此无需任何操作，直接输出 WWWWW。

思路

从右向左扫描

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string str;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> str;
	int i = str.rfind("WA");
	// 未找到WA位置
	if (i == -1) {
		cout << str << "\n";
		return 0;
	}

	while (str.rfind("WA") != -1) {
		i = str.rfind("WA");
		while (str[i] == 'W' && str[i + 1] == 'A') {
			str[i] = 'A', str[i + 1] = 'C';
			i--;
		}
	}

	cout << str << "\n";
	return 0;
}

D

算法标签: 栈

题目描述

给定一个由 6 种字符 (, ), [, ], <, > 组成的字符串 $S$。

当字符串 $T$ 满足以下条件时，称其为卡芙乐括号列：

通过执行以下操作若干次（包括零次）可以将 $T$ 变为空字符串：

• 若 $T$ 中存在连续的 (), [], <> 子字符串，选择其中任意一个删除。
• 若删除的子字符串位于 $T$ 的开头或结尾，则将剩余部分作为新的 $T$。
• 否则，将删除位置前后的字符串连接为新的 $T$。

请判断 $S$ 是否为卡芙乐括号列。

输入格式

输入通过标准输入按以下格式给出：

$S$

输出格式

若 $S$ 是卡芙乐括号列则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

([])<>()

输出 #1

Yes

输入输出样例 #2

输入 #2

([<)]>

输出 #2

No

输入输出样例 #3

输入 #3

())

输出 #3

No

说明/提示

约束条件

• $S$ 是长度介于 $1$ 到 $2\times 10^5$ 之间的字符串
• $S$ 仅由 (, ), [, ], <, > 组成

样例解释 1

对于 $S=$ ([])<>()，可通过以下操作变为空字符串：

• 删除第 2-3 字符 []，得到新字符串 ()<>()。
• 删除第 1-2 字符 ()，得到新字符串 <>()。
• 删除第 1-2 字符 <>，得到新字符串 ()。
• 删除 () 后字符串变为空。
  因此输出 Yes。

样例解释 2

$S=$ ([<)]> 不包含任何 (), [], <> 子字符串，无法执行任何操作，因此输出 No。

样例解释 3

无法通过操作将 $S=$ ><>< 变为空字符串，因此输出 No。

思路

栈对字符串进行匹配, 时间复杂度$O(n)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;

string str;
char stk[N];
int top;

bool cmp(char c1, char c2) {
	if (c1 == '(' && c2 == ')') return true;
	if (c1 == '[' && c2 == ']') return true;
	if (c1 == '<' && c2 == '>') return true;
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> str;
	top = -1;

	for (int i = 0; i < str.size(); ++i) {
		if (top != -1 && cmp(stk[top], str[i])) top--;
		else stk[++top] = str[i];
	}

	cout << (top == -1 ? "Yes" : "No") << "\n";

	return 0;
}

E

算法标签: $bfs$, 队列, 广度优先搜索

题目描述

给定一个包含 $N$ 个顶点的有向图，顶点编号为 $1,2,\dots ,N$。

边的信息由 $N^2$ 个字符 $C_{1,1},C_{1,2},\dots ,C_{1,N},C_{2,1},\dots ,C_{N,N}$ 给出。其中 $C_{i,j}$ 为小写字母或 -。

• 当 $C_{i,j}$ 为小写字母时，存在一条从顶点 $i$ 到顶点 $j$ 的边，且该边的标签为 $C_{i,j}$。
• 当 $C_{i,j}$ 为 - 时，不存在从顶点 $i$ 到顶点 $j$ 的边。

对于所有满足 $1\le i,j\le N$ 的整数对 $(i,j)$，请回答以下问题：

• 找出从顶点 $i$ 到顶点 $j$ 的路径（不要求是简单路径），使得路径上边标签按顺序组成的字符串是回文。在所有满足条件的路径中，输出最短路径的长度。若不存在这样的路径，输出 $-1$。

输入格式

输入通过标准输入按以下格式给出：

$N$
$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,N}$
$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,N}$
$⋮$
$C_{N,1}$ $C_{N,2}$ $\dots$ $C_{N,N}$

输出格式

以整数对 $(i,j)$ 的答案 $A_{i,j}$ 按以下格式输出：

$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,N}$
$⋮$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,N}$

输入输出样例 #1

输入 #1

4
ab--
--b-
---a
c---

输出 #1

0 1 2 4
-1 0 1 -1
3 -1 0 1
1 -1 -1 0

输入输出样例 #2

输入 #2

5
us---
-st--
--s--
u--s-
---ts

输出 #2

0 1 3 -1 -1
-1 0 1 -1 -1
-1 -1 0 -1 -1
1 3 -1 0 -1
-1 -1 5 1 0

说明/提示

约束条件

• $1\le N\le 100$
• $N$ 为整数
• $C_{i,j}$ 为小写字母或 -

样例解释 1

以 $(i,j)=(1,4)$ 为例：路径 $1\to 1\to 2\to 3\to 4$ 的边标签组成的字符串为 abba，这是一个回文。由于不存在长度小于 $4$ 的满足条件的路径，因此 $(i,j)=(1,4)$ 的答案为 $4$。注意空字符串也被视为回文。

思路

求回文路径的最短长度, 不存在就是$-1$

首先考虑简单情况, 什么时候答案是$0$?
$(1,1),(2,2),...,(i,i)$这些点到达自身答案一定是$0$

什么时候答案是$1$?
两个点直接相连的的边答案就是$1$

答案是$2$的情况

答案是$3$的情况

因此可以创建一个队列, 我们希望对所有二元组$(i,j)$求回文最短路, 对于每个状态搜索能转移到哪个状态, 二元组时间复杂度$O(n^2)$, 暴力枚举能转移到的状态$O(n^2)$, 总的时间复杂度$O(n^4)$, 数据范围$N\le 100$, 可以通过

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
const int N = 110, INF = 0x3f3f3f3f;

int n;
string w[N];
PII q[N * N];
int res[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

	memset(res, 0x3f, sizeof res);

    int h = 0, t = -1;
    for (int i = 0; i < n; ++i) {
        res[i][i] = 0;
        q[++t] = {i, i};
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            if (w[i][j] != '-') {
                res[i][j] = 1;
                q[++t] = {i, j};
            }
        }
    }

    while (h <= t) {
        auto [u, v] = q[h++];

        for (int i = 0; i < n; ++i) {
            if (w[i][u] == '-') continue;
            for (int j = 0; j < n; ++j) {
                if (w[v][j] == '-' || res[i][j] != INF) continue;

                // 找到了一个能够转移的位置
                if (w[i][u] == w[v][j]) {
                    res[i][j] = res[u][v] + 2;
                    q[++t] = {i, j};
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << (res[i][j] == INF ? -1 : res[i][j]) << " ";
        }

        cout << "\n";
    }

    return 0;
}

F

算法标签: 贪心, 树形$dp$

题目描述

给定一棵包含 $N$ 个顶点的无向树 $T$。顶点编号为 $1,2,\dots ,N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

定义满足以下两个条件的图为烷烃：

• 该图是一棵无向树
• 所有顶点的度数为 $1$ 或 $4$，且至少存在一个度数为 $4$ 的顶点

请判断 $T$ 中是否存在满足烷烃定义的子图。若存在，求此类子图的顶点数的最大值；否则输出 $-1$。

输入格式

输入通过标准输入按以下格式给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$⋮$
$A_{N-1}$ $B_{N-1}$

输出格式

若存在满足烷烃定义的子图，输出其顶点数的最大值；否则输出 $-1$。

输入输出样例 #1

输入 #1

9
1 2
2 3
3 4
4 5
2 6
2 7
3 8
3 9

输出 #1

8

输入输出样例 #2

输入 #2

7
1 2
1 3
2 4
2 5
3 6
3 7

输出 #2

-1

输入输出样例 #3

输入 #3

15
8 5
2 9
1 12
6 11
9 3
15 1
7 12
7 13
10 5
6 9
5 1
1 9
4 5
6 14

输出 #3

11

说明/提示

约束条件

• $1\le N\le 2\times 10^5$
• $1\le A_i,B_i\le N$
• 输入的图是一棵无向树
• 所有输入值为整数

样例解释 1

选取顶点 $1,2,3,4,6,7,8,9$ 及边 $(1,2)$、$(2,3)$、$(3,4)$、$(2,6)$、$(2,7)$、$(3,8)$、$(3,9)$ 构成的子图满足烷烃条件。其中顶点 $2$ 和顶点 $3$ 的度数为 $4$，其余顶点度数为 $1$，因此顶点数的最大值为 $8$。

思路

上述图就是一个烷烃, 如果选出主干, 那么总点数就是$3m+2$, 因此问题转化为如何求最大主干, 因此考虑将$deg[u]\ge 4$的点的连通块, 并且选出点的子图中, $deg$不能大于$4$

上图是所有主干的子图, 树形$dp$状态表示: $f[u][0]$选择当前点, 最大主干的大小, $f[u][1]$选择当前点, 留一个$deg$给父亲, 也就是最多选择$3$个子树

如何进行状态转移

1. $f[u][0]$, 因为选择当前点但是子节点选择没有限制, 设子节点$v$, 选出最大的四个$f[v][1]$
2. $f[u][1]$, 只能最多选择$3$个儿子, 也是贪心最大的$3$个儿子选择

m = max ⁡ u { f [ u ] [ 0 ] } m = \max _{u} \left \{ f[u][0] \right \} m=umax​{f[u][0]}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 2e5 + 10, M = N << 1;

int n;
int head[N], edge_end[M], next_edge[M], edge_index;
int deg[N];
int res;
int f[N][2];
bool vis[N];

void add(int u, int v) {
	edge_end[edge_index] = v, next_edge[edge_index] = head[u], head[u] = edge_index++;
}

void dfs(int u) {
	vis[u] = true;
	vector<int> s;

	for (int i = head[u]; ~i; i = next_edge[i]) {
		int ver = edge_end[i];
		if (deg[ver] >= 4 && !vis[ver]) {
			dfs(ver);
			// 留出一条边给父亲因此是f[ver][1]
			s.push_back(f[ver][1]);
		}
	}

	sort(s.begin(), s.end(), greater<int>());

	// 选出三个最大的儿子
	f[u][1] = 1;
	for (int i = 0; i < 3 && i < s.size(); ++i) f[u][1] += s[i];

	// 能选择四个
	f[u][0] = f[u][1];
	if (s.size() >= 4) f[u][0] += s[3];
	res = max(res, f[u][0]);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);

	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
		deg[u]++, deg[v]++;
	}

	for (int i = 1; i <= n; ++i) {
		if (deg[i] >= 4 && !vis[i]) dfs(i);
	}

	cout << (res == 0 ? -1 : res * 3 + 2) << "\n";
	return 0;
}

G

算法标签: 整体二分, 倍增, 最小瓶颈路, $lca$

题目描述

在东西南北方向被划分为 $H\times W$ 个区域的街区中，每个区域恰好建有一座大楼。
具体来说，北起第 $i$ 行（$1\le i\le H$）西起第 $j$ 列（$1\le j\le W$）的区域（以下简称区域 $(i,j)$）建有一座 $F_{i,j}$ 层的大楼。

高桥君有两种移动方式。当他在区域 $(i,j)$ 大楼的 $X$ 层（$1\le X\le F_{i,j}$）时，可以进行以下移动：

• 通过楼梯在同一大楼内移动到相邻的上一层或下一层。但无法从 $1$ 层移动到更下层，也无法从 $F_{i,j}$ 层移动到更上层。
• 通过 （高空）通道 移动到东西南北相邻区域中某座高度至少为 $X$ 层的大楼的 $X$ 层。

此处，区域 $(i,j)$ 与区域 $(i^{\prime },j^{\prime })$ 东西南北相邻的定义为 $|i-i^{\prime }|+|j-j^{\prime }|=1$。

请回答 $Q$ 个查询。第 $i$ 个（$1\le i\le Q$）查询内容如下：

请求出高桥君从区域 $(A_i,B_i)$ 大楼的 $Y_i$ 层移动到区域 $(C_i,D_i)$ 大楼的 $Z_i$ 层时，楼梯使用次数的最小可能值。
注意：每次上下移动一层均计为一次楼梯使用（例如从某大楼 $1$ 层移动到 $6$ 层需使用 $5$ 次楼梯）。
同时，通道使用次数无需最小化。

输入格式

输入通过标准输入按以下格式给出：

$H$ $W$
$F_{1,1}$ $F_{1,2}$ $\dots$ $F_{1,W}$
$F_{2,1}$ $F_{2,2}$ $\dots$ $F_{2,W}$
$⋮$
$F_{H,1}$ $F_{H,2}$ $\dots$ $F_{H,W}$
$Q$
$A_1$ $B_1$ $Y_1$ $C_1$ $D_1$ $Z_1$
$A_2$ $B_2$ $Y_2$ $C_2$ $D_2$ $Z_2$
$⋮$
$A_Q$ $B_Q$ $Y_Q$ $C_Q$ $D_Q$ $Z_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

3 3
12 10 6
1 1 3
8 6 7
2
1 1 10 3 1 6
1 1 6 1 2 4

输出 #1

10
2

说明/提示

约束条件

• $1\le H\le 500$
• $1\le W\le 500$
• $1\le F_{i,j}\le 10^6$
• $1\le Q\le 2\times 10^5$
• $1\le A_i,C_i\le H$
• $1\le B_i,D_i\le W$
• $1\le Y_i\le F_{A_i,B_i}$
• $1\le Z_i\le F_{C_i,D_i}$
• $(A_i,B_i,Y_i)\ne (C_i,D_i,Z_i)$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个查询，以下移动方式共使用 $10$ 次楼梯：

• 通过通道从区域 $(1,1)$ 大楼 $10$ 层移动到区域 $(1,2)$ 大楼 $10$ 层
• 使用 $4$ 次楼梯从 $10$ 层下到 $6$ 层
• 通过通道移动到区域 $(1,3)$ 大楼 $6$ 层
• 使用 $3$ 次楼梯下到 $3$ 层
• 通过通道移动到区域 $(2,3)$ 大楼 $3$ 层
• 通过通道移动到区域 $(3,3)$ 大楼 $3$ 层
• 使用 $3$ 次楼梯上到 $6$ 层
• 通过通道移动到区域 $(3,2)$ 大楼 $6$ 层
• 通过通道移动到区域 $(3,1)$ 大楼 $6$ 层
  由于无法用 $9$ 次或更少楼梯完成移动，故输出 $10$。

对于第 $2$ 个查询，通过通道移动到区域 $(1,2)$ 大楼后，使用 $2$ 次楼梯从 $6$ 层下到 $4$ 层即可完成移动，故输出 $2$。

思路

比较直观的是动态规划$f[i][j][k]$代表到达位置$(i,j)$层数是$k$的最小走动楼梯数, 从当前位置开始递推走到目标位置, 但是查询数量$2\times 10^5$, 总的时间复杂度$500\times 500\times 10^5\times 2\times 10^5$一定会超时

对于相邻的两栋楼房来说, 能够互相到达取决于楼层高度较小的那一栋楼, 因此最优的方案一定是从开始位置下楼然后走通道, 然后再上楼, 为了使使用楼梯次数最小, 需要最大化最小高度也就是最小瓶颈路, 跑最大生成树, 最大生成树确定后两点之间的距离就确定, 那么使用倍增算法求路径上最小值即可, 时间复杂度$O(\log n)$

为什么最大生成树上的路径一定是最优的?
假设路径选择了另一条非最大生成树边, 记为$(u,v)$, 那么因为最大生成树将所有点连通, 因此必然存在一条$(u^{\prime },v^{\prime })$边权是大于等于$(u,v)$, 通过有限次变换一定可以将所有边变换为最大生成树的边, 因此最大生成树的边就是最优路径

最小瓶颈路的模板题

P1967 [NOIP 2013 提高组] 货车运输

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 $m$ 条道路。

接下来 $m$ 行每行三个整数 $x,y,z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x\ne y$，两座城市之间可能有多条道路 。

接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x\ne y$

输出格式

共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-1$。

输入输出样例 #1

输入 #1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出 #1

3
-1
3

说明/提示

对于 $30\%$ 的数据，$1\le n<1000$，$1\le m<10,000$，$1\le q<1000$；

对于 $60\%$ 的数据，$1\le n<1000$，$1\le m<5\times 10^4$，$1\le q<1000$；

对于 $100\%$ 的数据，$1\le n<10^4$，$1\le m<5\times 10^4$，$1\le q<3\times 10^4$，$0\le z\le 10^5$。

模板题代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e4 + 10, M = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
struct Edge {
	int u, v, w;
	bool operator< (const Edge e) {
		return w > e.w;
	}
} edges[M];
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
int p[N];
// 记录最近公共祖先, 以及每个点到最近公共祖先的最小边权
int fa[N][16], d[N][16];
int depth[N];
bool vis[N];

void add(int u, int v, int val) {
	edge_end[edge_index] = v, next_edge[edge_index] = head[u], w[edge_index] = val, head[u] = edge_index++;
}

int find(int u) {
	if (p[u] != u) p[u] = find(p[u]);
	return p[u];
}

void kruskal() {
	for (int i = 1; i <= n; ++i) p[i] = i;
	sort(edges, edges + m);

	for (int i = 0; i < m; ++i) {
		int u = edges[i].u;
		int v = edges[i].v;
		int w = edges[i].w;

		int fa1 = find(u), fa2 = find(v);
		if (fa1 != fa2) {
			add(u, v, w);
			add(v, u, w);
			p[fa2] = fa1;
		}
	}
}

void dfs(int u) {
	vis[u] = true;
	for (int i = head[u]; ~i; i = next_edge[i]) {
		int ver = edge_end[i];
		if (vis[ver]) continue;
		depth[ver] = depth[u] + 1;
		fa[ver][0] = u;
		d[ver][0] = w[i];
		dfs(ver);
	}
}

int lca(int u, int v) {
	if (find(u) != find(v)) return -1;
	if (depth[u] < depth[v]) swap(u, v);

	int res = INF;
	for (int k = 15; k >= 0; --k) {
		if (depth[fa[u][k]] >= depth[v]) {
			res = min(res, d[u][k]);
			u = fa[u][k];
		}
	}

	if (u == v) return res;

	for (int k = 15; k >= 0; --k) {
		if (fa[u][k] != fa[v][k]) {
			res = min({res, d[u][k], d[v][k]});
			u = fa[u][k];
			v = fa[v][k];
		}
	}

	res = min({res, d[u][0], d[v][0]});
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);

	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		edges[i] = {u, v, w};
	}

	kruskal();
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			depth[i] = 1;
			dfs(i);
			fa[i][0] = i;
			d[i][0] = INF;
		}
	}

	// 倍增
	for (int k = 1; k <= 15; ++k) {
		for (int i = 1; i <= n; ++i) {
			fa[i][k] = fa[fa[i][k - 1]][k - 1];
			d[i][k] = min(d[i][k - 1], d[fa[i][k - 1]][k - 1]);
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		int res = lca(x, y);
		if (res == INF) res = -1;
		cout << res << "\n";
	}

	return 0;
}

本题代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int R = 505, N = R * R, K = 18, INF = 0x3f3f3f3f;

int r, c;
int h[R][R], id[R][R];
struct Edge {
	int u, v, w;

	bool operator<(const Edge &e) const {
		return w > e.w;
	}
};
vector<Edge> edges;
vector<PII> head[N];
int p[N], depth[N], fa[N][K], w[N][K];
bool vis[N];

void init() {
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			id[i][j] = (i - 1) * c + j;
		}
	}
}

void build() {
	for (int i = 1; i < r; ++i) {
		for (int j = 1; j <= c; ++j) {
			int u = id[i][j], v = id[i + 1][j];
			edges.push_back({u, v, min(h[i][j], h[i + 1][j])});
		}
	}

	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j < c; ++j) {
			int u = id[i][j], v = id[i][j + 1];
			edges.push_back({u, v, min(h[i][j], h[i][j + 1])});
		}
	}
}

void add(int u, int v, int w) {
	head[u].push_back({v, w});
	head[v].push_back({u, w});
}

int find(int u) {
	if (p[u] != u) p[u] = find(p[u]);
	return p[u];
}

void kruskal() {
	for (int i = 1; i <= r * c; ++i) p[i] = i;
	sort(edges.begin(), edges.end());

	for (auto [u, v, w] : edges) {
		int fa1 = find(u), fa2 = find(v);
		if (fa1 == fa2) continue;
		p[fa2] = fa1;
		add(u, v, w);
	}
}


void dfs(int u) {
	vis[u] = true;
	for (auto [v, val] : head[u]) {
		if (vis[v]) continue;
		depth[v] = depth[u] + 1;
		fa[v][0] = u;
		w[v][0] = val;
		dfs(v);
	}
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);

	int res = INF;
	for (int k = K - 1; k >= 0; --k) {
		if (depth[fa[u][k]] >= depth[v]) {
			res = min(res, w[u][k]);
			u = fa[u][k];
		}
	}

	if (u == v) return res;

	for (int k = K - 1; k >= 0; --k) {
		if (fa[u][k] != fa[v][k]) {
			res = min({res, w[u][k], w[v][k]});
			u = fa[u][k];
			v = fa[v][k];
		}
	}

	res = min({res, w[u][0], w[v][0]});
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> r >> c;
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			cin >> h[i][j];
		}
	}

	// 二维平面做康托展开
	init();

	// 构建图
	build();

	// 跑最大生成树
	kruskal();

	// 初始化倍增数组
	memset(w, 0x3f, sizeof w);
	depth[1] = 1;
	dfs(1);

	for (int k = 1; k < K; ++k) {
		for (int i = 1; i <= r * c; ++i) {
			int mid = fa[i][k - 1];
			fa[i][k] = fa[mid][k - 1];
			w[i][k] = min(w[i][k - 1], w[mid][k - 1]);
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int a, b, c, a1, b1, c1;
		cin >> a >> b >> c >> a1 >> b1 >> c1;

		int u = id[a][b];
		int v = id[a1][b1];
		int layer = lca(u, v);
		layer = min({layer, c, c1});

		int res = c - layer + c1 - layer;
		cout << res << "\n";
	}

	return 0;
}