題目鏈接

題目難度

洛谷上是藍題，本人認為評高了，此題思維和實現都不難，應該是綠題。

題目解法概括

kruskal 重構樹 + 倍增優化求路徑最小邊權

代碼

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;typedef long long LL;const LL Maxn = 1e4 + 5;
const LL Maxm = 5 * 1e4 + 5;
const LL Maxk = 20;
const LL Inf = 1e18;struct node {LL x, y, z;
} Edge[Maxm];struct node2 {LL to, e;
};
vector<node2> tree[Maxn];LL bfa[Maxn], father[Maxn][Maxk], depth[Maxn], minDis[Maxn][Maxk];
bool vis[Maxn];void init_bfa(LL n) {for (LL i = 0; i <= n; ++i)  bfa[i] = i;return;
}LL f_find(LL x) {if (x == bfa[x])  return x;else  return bfa[x] = f_find(bfa[x]);
}bool f_join(LL u, LL v) {u = f_find(u);v = f_find(v);if (u == v)  return false;bfa[u] = v;return true;
}void dfs(LL u, LL fa) {vis[u] = true;father[u][0] = fa;depth[u] = depth[fa] + 1;for (LL i = 1; depth[u] > (1 << i); ++i) {father[u][i] = father[father[u][i - 1]][i - 1];minDis[u][i] = min(minDis[u][i - 1], minDis[father[u][i - 1]][i - 1]);}for (auto elem : tree[u]) {if (elem.to == fa)  continue;minDis[elem.to][0] = elem.e;dfs(elem.to, u);}return;
}LL path_num(LL u, LL v) {if (depth[u] < depth[v])  swap(u, v);LL res = Inf;for (LL i = Maxk - 1; i >= 0; --i) {if (depth[father[u][i]] >= depth[v]) {res = min(res, minDis[u][i]);u = father[u][i];}}if (u == v)  return res;for (LL i = Maxk - 1; i >= 0; --i) {if (father[u][i] != father[v][i]) {res = min(res, min(minDis[u][i], minDis[v][i]));u = father[u][i];v = father[v][i];}}if (father[u][0] == 0)  return -1;else {res = min(res, min(minDis[u][0], minDis[v][0]));return res;}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, q, a, b;cin >> n >> m;for (LL i = 1; i <= m; ++i) {cin >> Edge[i].x >> Edge[i].y >> Edge[i].z;}sort(Edge + 1, Edge + m + 1, [](const node& a, const node& b) {return a.z > b.z;});init_bfa(n);for (LL i = 1; i <= m; ++i) {if (f_join(Edge[i].x, Edge[i].y) != false) {tree[Edge[i].x].push_back({Edge[i].y, Edge[i].z});tree[Edge[i].y].push_back({Edge[i].x, Edge[i].z});}}for (LL i = 1; i <= n; ++i) {if (vis[i] == false)  dfs(i, 0);}cin >> q;while (q--) {cin >> a >> b;cout << path_num(a, b) << '\n';}return 0;
}

總結

只考慮和結果有關的部分，是此題的突破點，也是重要的思維方式。

解法

若 x 到 y 有多條路徑，只需考慮最小邊權最大的路徑，直接找這樣的路徑，比較費時，可以考慮直接去掉無用的路徑，那么用 kruskal 重構樹構建最大瓶頸樹。我們只考慮和結果有關的部分。

此時，問題就變成了樹上的求路徑的最小邊權問題，需要求 LCA，求 LCA 和求路徑的最小邊權可以同步進行。