题目链接：https://vjudge.net/problem/UVA-11354
题意：给出一张图，q个询问，每次询问给出uv，找出一条路径，使这条路径上的最大边权是两点所有路径中最小，输出这个值
思路：很显然要先求出最小生成树，任意两点在最小生成树上有唯一路径，并且这条路径上的最大边权就是所输出的值，接下来就是如何求出树上任意两点唯一路径中的最大边权了，先把最小生成树转化为有根树，并用fa数组表示u的父亲节点，cost数组表示与父亲节点连的边的边权，dep数组表示这个点的深度，对于每次查询，先把两点的深度调到一样大，同时更新最大边，然后一起向上搜索直到两点的最近公共祖先，同时也更新最大边。这就是最朴素的求LCA的方法。
#include <bits/stdc++.h> using namespace std; const int MAXN = 50005; const int MAXM = 100005; struct Edge { int from,to,w; int Next; }edge[MAXM],e[MAXM]; int n,pre[MAXN],m; int head[MAXN],tot; int fa[MAXN],cost[MAXN],dep[MAXN]; void init() { tot = 0; memset(head,-1,sizeof(head)); for(int i = 1; i <= n; i++) { pre[i] = i; } } bool cmp(struct Edge a,struct Edge b) { return a.w < b.w; } void addedge(int u,int v,int w) { e[tot].from = u; e[tot].to = v; e[tot].w = w; e[tot].Next = head[u]; head[u] = tot++; } inline int Find(int x) { if(x == pre[x]) return x; else return pre[x] = Find(pre[x]); } void kruskal() { sort(edge + 1,edge + 1 + m,cmp); int fu,fv,u,v; for(int i = 1; i <= m; i++) { u = edge[i].from; v = edge[i].to; fu = Find(u); fv = Find(v); if(fu != fv) { pre[fu] = fv; addedge(u,v,edge[i].w); addedge(v,u,edge[i].w); } } } void dfs(int u,int Fa,int step) { int v; for(int i = head[u]; i != -1; i = e[i].Next) { v = e[i].to; if(v == Fa) continue; dep[v] = step; fa[v] = u; cost[v] = e[i].w; dfs(v,u,step + 1); } } int query(int u,int v) { int du = dep[u]; int dv = dep[v]; int res = 0; while(du > dv) { res = max(res,cost[u]); u = fa[u]; du--; } while(dv > du) { res = max(res,cost[v]); v = fa[v]; dv--; } while(u != v) { res = max(res,cost[u]); res = max(res,cost[v]); u = fa[u]; v = fa[v]; } return res; } int main(void) { int u,v,w,q; int flag = 0; while(scanf("%d %d",&n,&m) != EOF) { if(flag) printf("\n"); flag = 1; init(); for(int i = 1; i <= m; i++) { scanf("%d %d %d",&u,&v,&w); edge[i].from = u; edge[i].to = v; edge[i].w = w; } kruskal(); fa[1] = cost[1] = dep[1] = 0; dfs(1,-1,1); scanf("%d",&q); while(q--) { scanf("%d %d",&u,&v); printf("%d\n",query(u,v)); } } return 0; } /* 4 5 1 2 10 1 3 20 1 4 100 2 4 30 3 4 10 2 1 4 4 1 2 1 1 2 100 */
