目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
2.网络稳定性 - 蓝桥云课 (lanqiao.cn)
二、解题报告
1、思路分析
考虑到如果给一棵树，查询任意两点间路径上最小边权，可以用倍增法+LCA来解决
但是给了一个图，又考虑到题目要求的是所有路径种最大的最小边权
那么对于两点间路径我们只需要保留最大的那一条即可
所以我们可以用Kruscal求最大生成树
然后套倍增法求LCA的板子即可
2、复杂度
时间复杂度： O((q+ n)logn + mlogm)空间复杂度：O(nlogn + m)
3、代码详解
#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <vector>
using namespace std;
const int N = 1e5 + 10, M = 3e5 + 10;
typedef pair<int,int> pii;
struct edge{int u, v, w;bool operator <(const edge& e)const{return w > e.w;}
}edges[M];
vector<pii> g[N];
int n, m, q, p[N], dep[N]{0}, f[N][20]{0}, cost[N][20]{0};
bitset<N> vis;
int findp(int x){return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void merge(int x, int y){int px = findp(x), py = findp(y);if(px == py) return;if(p[px] > p[py]) swap(px, py);p[px] += p[py], p[py] = px;
}
void Kruscal(){sort(edges, edges + m);for(int i = 0, a, b, c; i < m; i++){a = edges[i].u, b = edges[i].v, c = edges[i].w;if(findp(a) == findp(b)) continue;merge(a, b);g[a].emplace_back(b, c), g[b].emplace_back(a, c);}
}
void dfs(int x, int fa){vis[x] = 1, dep[x] = dep[fa] + 1, f[x][0] = fa;for(int i = 1; i < 20; i++)f[x][i] = f[f[x][i-1]][i-1], cost[x][i] = min(cost[x][i - 1], cost[f[x][i-1]][i-1]);for(auto& [y, w] : g[x])if(y != fa)cost[y][0] = w, dfs(y, x);
}
int lca(int x, int y){if(dep[x] < dep[y]) swap(x, y);int ret = cost[x][0];for(int i = 19; i >= 0; i--)if(dep[f[x][i]] >= dep[y]) ret = min(ret, cost[x][i]), x = f[x][i];if(x == y) return ret;for(int i = 19; i >= 0; i--)if(f[x][i] != f[y][i]) ret = min(ret, min(cost[x][i], cost[y][i])), x = f[x][i], y = f[y][i];ret = min(ret, min(cost[x][0], cost[y][0]));return ret;
}
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(p, -1, sizeof p);cin >> n >> m >> q;for(int i = 0, a, b, c; i < m; i++) cin >> a >> b >> c, edges[i] = {a, b, c};Kruscal();for(int i = 1; i <= n; i++)if(!vis[i]) dfs(i, 0);for(int i = 0, a, b; i < q; i++){cin >> a >> b;if(findp(a) != findp(b)) cout << "-1\n";else cout << lca(a, b) << '\n';}return 0;
}
