# UVA - 11354 Bond （最小生成树+朴素LCA）

xiaoxiao2021-03-01  19

题目链接：https://vjudge.net/problem/UVA-11354

#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 */