……
2026-02-03 20:58:21
发布于：浙江
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 10;
const int LOG = 20; // 2^20 > 2e5，足够覆盖所有节点深度
// 并查集（Kruskal用，路径压缩+按秩合并）
struct DSU {
vector<int> fa, siz;
DSU(int n) {
fa.resize(n + 1);
siz.resize(n + 1, 1);
for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return false;
if (siz[v] > siz[u]) swap(u, v);
fa[v] = u;
siz[u] += siz[v];
return true;
}
bool same(int u, int v) {
return find(u) == find(v);
}
};
// 边的结构体（Kruskal排序用）
struct Edge {
int u, v, w;
bool operator<(const Edge& b) const {
return w < b.w;
}
};
// MST的邻接表：pair<邻接点, 边权>
vector<pair<int, int>> g[MAXN];
// 倍增数组：up[k][u] = u的2^k级祖先，maxw[k][u] = u到2^k级祖先的最大边权
int up[LOG][MAXN];
int maxw[LOG][MAXN];
// 节点深度
int dep[MAXN];
int n, m, q;
// 深搜预处理倍增数组（从根节点1开始，可任选根）
void dfs(int u, int fa, int w) {
up[0][u] = fa; // 2^0级祖先 = 直接父节点
maxw[0][u] = w; // 到直接父节点的边权
dep[u] = dep[fa] + 1; // 深度=父节点深度+1
// 预处理2^1 ~ 2^(LOG-1)级祖先
for (int k = 1; k < LOG; k++) {
up[k][u] = up[k-1][up[k-1][u]];
maxw[k][u] = max(maxw[k-1][u], maxw[k-1][up[k-1][u]]);
}
// 遍历子节点
for (auto& e : g[u]) {
int v = e.first, val = e.second;
if (v != fa) {
dfs(v, u, val);
}
}
}
// 求a和b的LCA，并返回路径上的最大边权（最小瓶颈值）
int query(int a, int b) {
if (a == b) return 0; // 自身到自身，瓶颈值0
if (!DSU(n).same(a, b)) return -1; // 不连通，返回-1（实际可提前判断）
int res = 0;
// 先将a和b提到同一深度，同步记录最大边权
if (dep[a] < dep[b]) swap(a, b);
for (int k = LOG-1; k >= 0; k--) {
if (dep[up[k][a]] >= dep[b]) {
res = max(res, maxw[k][a]);
a = up[k][a];
}
}
if (a == b) return res;
// 同时上跳，直到找到LCA，同步记录最大边权
for (int k = LOG-1; k >= 0; k--) {
if (up[k][a] != up[k][b]) {
res = max(res, max(maxw[k][a], maxw[k][b]));
a = up[k][a];
b = up[k][b];
}
}
// 最后跳一步到LCA，加上最后两条边的权值
res = max(res, max(maxw[0][a], maxw[0][b]));
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m >> q;
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
// 步骤1：Kruskal求MST，构建邻接表
sort(edges.begin(), edges.end());
DSU dsu(n);
for (auto& e : edges) {
int u = e.u, v = e.v, w = e.w;
if (dsu.merge(u, v)) {
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
}
// 步骤2：倍增预处理（对每个连通块单独预处理，避免漏解）
memset(up, 0, sizeof(up));
memset(maxw, 0, sizeof(maxw));
memset(dep, 0, sizeof(dep));
for (int i = 1; i <= n; i++) {
if (dsu.find(i) == i) { // 根节点（每个连通块的代表元）
dfs(i, 0, 0); // 根节点的父节点为0，边权0
}
}
// 步骤3：处理q次询问
while (q--) {
int a, b;
cin >> a >> b;
if (a == b) {
cout << 0 << '\n';
continue;
}
if (!dsu.same(a, b)) {
cout << -1 << '\n';
continue;
}
cout << query(a, b) << '\n';
}
return 0;
}
这里空空如也
有帮助，赞一个