题解
题意
- 给你一个无向图，求两个点之间的一条路径，使路径上的最小值最大
算法：Kruskal最大生成树+倍增lca
分析
- 首先容易知道，答案一定在该图的最大生成树上
- 之后问题便转换成了树上点\(u\)到\(v\)的简单路径42中最小的边权
- 经典的树上倍增
- 用fa[i][j]来表示从第\(i\)个点往上\(2^j\)条边到达的点
- 用s[i][j]来表示从第\(i\)个点往上\(2^j\)条边中的最小值
- 答案就是在求lca的过程中统计一下最小值就可以了（具体详见代码）
复杂度：
Kruskal \(O(m \log m)\) 倍增 \(O(n \log n)\) 总复杂度 \(O(n \log n + m \log m)\)代码：#include#include #include #include using namespace std;const int MAXN = 50050;int n, m, q;int p[MAXN];int dep[MAXN], vis[MAXN], fa[MAXN][20], s[MAXN][20]; struct Edge{ int u, v, w; bool operator < (const Edge &_edge) const { return w > _edge.w; }}edge[MAXN];int ecnt;struct node{ int v, w; node *next;}pool[MAXN], *head[MAXN];void addedge(int u, int v, int w){ node *p = &pool[++ecnt], *q = &pool[++ecnt]; p->v = v, p->w = w, p->next = head[u], head[u] = p; q->v = u, q->w = w, q->next = head[v], head[v] = q;}int find(int x){ if(p[x] == 0) return x; else return p[x] = find(p[x]);}bool Union(int x, int y){ int px = find(x); int py = find(y); if(px == py) return false; p[px] = py; return true;}void dfs(int u){ int v; vis[u] = 1; for(node *p = head[u]; p; p = p->next) if(!vis[v = p->v]) { dep[v] = dep[u] + 1; fa[v][0] = u; s[v][0] = p->w; for(int j = 1; fa[v][j - 1] != 0; j++) fa[v][j] = fa[fa[v][j - 1]][j - 1], s[v][j] = min(s[v][j - 1], s[fa[v][j - 1]][j - 1]); //预处理 dfs(v); }}int query(int u, int v)//倍增{ int ret = 2147483647;//返回值。因为求最小，所以初始赋最大 if(dep[u] < dep[v]) swap(u, v); for(int i = 15; i >= 0; i--) if(fa[u][i] != 0 && dep[fa[u][i]] >= dep[v]) ret = min(ret, s[u][i]), u = fa[u][i];//一定要先统计最小值 if(u == v) return ret; for(int i = 15; i >= 0; i--) if(fa[u][i] != fa[v][i]) ret = min(ret, min(s[u][i], s[v][i])), //统计最小 u = fa[u][i], v = fa[v][i]; ret = min(ret, min(s[u][0], s[v][0]));//不要忘了最后还有两条边 return ret;}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); sort(edge + 1, edge + m + 1); for(int i = 1; i <= m; i++) if(Union(edge[i].u, edge[i].v)) addedge(edge[i].u, edge[i].v, edge[i].w); dfs(1); scanf("%d", &q); for(int i = 1; i <= q; i++) { int u, v; scanf("%d%d", &u, &v); if(find(u) != find(v)) { printf("-1\n"); continue ; } printf("%d\n", query(u, v)); } return 0;}