只有std，没有自我实现，所以叫做无码专区
description
给一张无向图，多次询问，每次询问两个点之间所有简单路径（不重复经过点）中边权第二大（不是严格第二大）的权值的最小值。
数据范围： 1 0 5 10^5 105 级别
我的想法
前 50 % 50\% 50% 的数据 q , n ≤ 1 0 3 , m ≤ 2 × 1 0 3 : q,n\le 10^3,m\le 2\times 10^3: q,n≤103,m≤2×103:
先做一次最小生成树，求出任意两点之间联通的最小边权（某条路径的最大边权值）。
每次询问 ( u , v ) (u,v) (u,v) ，我直接枚举中间转折点 i i i，强制这条路径是 u → i → v u\rightarrow i\rightarrow v u→i→v。【 → \rightarrow → 代指一条路径】
第二大边权就是 ( u , i ) (u,i) (u,i) 联通路径的最大值和 ( v , i ) (v,i) (v,i) 联通路径的最大值，二者中的较小值。
旁边的 Oxide \text{Oxide} Oxide 巨佬认为很有可能 u → i u\rightarrow i u→i 和 i → w i\rightarrow w i→w 之间经过了同样的点。
i.e.
u
→
x
→
i
→
x
→
v
u\rightarrow x\rightarrow i \rightarrow x\rightarrow v
u→x→i→x→v
但后面再仔细一想，就算这是的答案会被 i i i 更新，但是后面一定会枚举到 x x x，显然 u → x → v u\rightarrow x\rightarrow v u→x→v 会比以前的路径少了 ( x , i ) (x,i) (x,i) 一段。
路径上的边权最大值一定是不减的
所以多的 ( x , i ) (x,i) (x,i) 一段只可能使最大边权增大 / 不变。
那么 x x x 的决策一定是不劣于 i i i 的决策的。
另有 20 % 20\% 20% 是树：两个点之间只有一条简单路径，可以直接倍增求路径的第二大边权值。
综上，本题自我实现分值应该在 7 0 ′ 70' 70′。
solution
类似最小生成树的方法，从小到大加边。
如果加完一条边后， u , v u,v u,v 之间只差一条边联通，那么显然这条边就是第二小，也就是最终的答案。
考虑怎么维护？
设 N ( u ) : N(u): N(u): 与 u u u 有直接边相连，但还没有相连的点的集合【当前枚举边的权值暂时小于等于这些点与 u u u 的权值，最小生成树的写法就还没有加入这些边】
或者理解为：还差一条边就能联通的点的集合
考虑启发式合并，每次合并 u , v u,v u,v 各自所在的连通块。
此时可能出现： N ( u ) N(u) N(u) 中的点 x x x 与 v v v 相连【在 v v v 连通块里面】 ，或， N ( v ) N(v) N(v) 中的点 y y y 与 u u u 相连【在 u u u 连通块里面】
这个时候意味着，加上 u − v u-v u−v 这条边后，还差 u − x u-x u−x 或 v − y v-y v−y 这一条边就会使得 u , v u,v u,v 相连，所以 u − v u-v u−v 这条边权就是最后的答案。
如果直接枚举 N ( u ) , N ( v ) N(u),N(v) N(u),N(v) 则不符合时间限制。
我们可以这么做：
-
遍历 N ( u ) N(u) N(u) 的所有点，然后看是否在 v v v 的询问中。
i.e.假设 x ∈ N ( u ) , x ∈ q ( v ) x\in N(u),x\in q(v) x∈N(u),x∈q(v) ， x − u x-u x−u 之间的边还没有加入。此时加入为 u − v u-v u−v 的边。一旦加入完， x → u → v x\rightarrow u\rightarrow v x→u→v就只差 x − u x-u x−u 的一条边。
所以答案就是现在操作的 u − v u-v u−v 边的边权。
这样就处理了挂在 v v v 上面的某些 通过 u u u 连通块中某些点和边解决 的询问。
-
遍历 u u u 里面的所有询问，判断是否在 N ( v ) N(v) N(v) 中。
i.e.假设 x ∈ q ( u ) x\in q(u) x∈q(u) ， x − v x-v x−v 之间的边还没有加入。此时加入为 u − v u-v u−v 的边。一旦加入完， x → v → u x\rightarrow v\rightarrow u x→v→u 就只差 x − v x-v x−v 的一条边。
所以答案是 u − v u-v u−v 现在这条边的边权。
这样就处理了挂在 u u u 上面的某些 通过 v v v 连通块中某些点和边解决 的询问。
这么做会发现，虽然是合并两个联通块和处理两个联通块各自挂着的询问，但是枚举的只有一个联通块的信息。
所以启发式合并，就用 N ( u ) + q ( u ) N(u)+q(u) N(u)+q(u) 和 N ( v ) + q ( v ) N(v)+q(v) N(v)+q(v) 大小比较，选较小的进行枚举。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
合并具体而言：枚举其中一个较小连通块的信息，进行答案处理。所有挂在 u , v u,v u,v 点的询问和边都重新挂在合并后新连通块的根 w w w 上。
i.e. 询问
u
,
x
u,x
u,x 的答案，合并后相当于问
w
,
x
w,x
w,x 的答案，因为反正
u
−
w
u-w
u−w 的边权不是第二大。原本
u
−
x
u-x
u−x 的一条边，变成
w
−
x
w-x
w−x 的一条边。
所以上面的形如 x − u x-u x−u ：不一定表示原先加入的 m m m 条边就是 x − u x-u x−u，而是可能通过 x − a − b − c − . . . − u x-a-b-c-...-u x−a−b−c−...−u ，不断合并，可能代指的是一条简单路径。文章来源：https://www.toymoban.com/news/detail-475058.html
参考code文章来源地址https://www.toymoban.com/news/detail-475058.html
#include <bits/stdc++.h>
using namespace std;
#define N 400005
#define pb push_back
int fa[N];
struct node {
int x, y, z;
} b[N];
int ans[N], n, m, Q;
set<array<int, 2>> q[N];
set<int> e[N];
int get(int x) {
if (fa[x] == x)
return x;
return fa[x] = get(fa[x]);
}
inline bool cmp(node x, node y) {
return x.z < y.z;
}
void combine(int x, int y, int val) {
for (auto u : e[x]) {
while (1) {
auto it = q[y].lower_bound({u, -1});
if (it == q[y].end() || (*it)[0] != u)
break;
int id = (*it)[1];
ans[id] = val;
assert(q[y].count({u, id}));
assert(q[u].count({y, id}));
q[y].erase(it);
q[u].erase({y, id});
}
}
vector<array<int, 2>> delq;
for (auto u : q[x]) {
if (e[y].count(u[0])) {
ans[u[1]] = val;
q[u[0]].erase({x, u[1]});
delq.pb(u);
}
}
for (auto u : delq)
q[x].erase(u);
fa[x] = y;
for (auto v : e[x]) {
assert(e[v].count(x));
e[v].erase(x);
if (v != y) {
e[v].insert(y);
e[y].insert(v);
}
}
e[x].clear();
for (auto v : q[x]) {
assert(v[0] != y);
assert(q[v[0]].count({x, v[1]}));
q[v[0]].erase({x, v[1]});
q[v[0]].insert({y, v[1]});
q[y].insert({v[0], v[1]});
}
q[x].clear();
}
int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
scanf("%d%d%d", &n, &m, &Q);
for (int i = 1; i <= n; i++)
e[i].clear(), q[i].clear();
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
e[b[i].x].insert(b[i].y);
e[b[i].y].insert(b[i].x);
}
for (int i = 1; i <= n; i++)
fa[i] = i;
sort(b + 1, b + 1 + m, cmp);
for (int i = 1; i <= Q; i++) {
ans[i] = 0;
int x, y;
scanf("%d%d", &x, &y);
if (e[x].count(y)) {
ans[i] = 1;
continue;
}
q[x].insert({y, i});
q[y].insert({x, i});
}
for (int i = 1; i <= m; i++) {
b[i].x = get(b[i].x), b[i].y = get(b[i].y);
if (b[i].x == b[i].y)
continue;
if (q[b[i].x].size() + e[b[i].x].size() > q[b[i].y].size() + e[b[i].y].size())
swap(b[i].x, b[i].y);
combine(b[i].x, b[i].y, b[i].z + 1);
}
for (int i = 1; i <= Q; i++)
printf("%d\n", ans[i] - 1);
}
到了这里，关于【无码专区1】简单路径的第二大边权（启发式合并+最小生成树)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
