3732: Network
https://www.lydsy.com/JudgeOnline/problem.php?id=3732
分析：
最小生成树+倍增 或者 kruskal重构树。
1、可以求出最小最小生成树，然后倍增求出两条路径的最大值。
2、kruskal重构树，直接求出LCA即可。
kruskal重构树：在kruskal过程中，每次加边后，不直接连边，而是新建一个节点，节点的两个子节点分别为新边连接的两个联通块的根节点（并查集维护），节点的权值为这条边的权值。那么它有一些性质：
- 是一棵二叉树；
- 父节点的值大于等于子节点；
- 原图上两点间路径的最长边的最小值等于其lca的值；
那么这道题就可以建出kruskal重构树，后求出Lca即可。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 ?5 inline int read() { ?6 ????int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; 7 ????for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; 8 } 9 10 #define Rep(i,a,b) for (int i=(a); i<=(b); ++i)11 12 const int M = 30010;13 const int N = 15010;14 struct Edge{15 ????int u,v,w;16 ????bool operator < (const Edge &A) const {17 ????????return w < A.w;18 ????}19 }e[M];20 int fa[N<<1], deth[N<<1], f[N<<1][16], ch[N<<1][2], val[N<<1], CntNode;21 22 23 int find(int x) {24 ????return x == fa[x] ? x : fa[x] = find(fa[x]);25 }26 void dfs(int u) {27 ????if (!u) return ;28 ????deth[ch[u][0]] = deth[ch[u][1]] = deth[u] + 1;29 ????dfs(ch[u][0]);30 ????dfs(ch[u][1]);31 }32 33 int Lca(int u,int v) {34 ????if (deth[u] < deth[v]) swap(u, v);35 ????int d = deth[u] - deth[v];36 ????for (int j=15; j>=0; --j) {37 ????????if (d & (1 << j)) u = f[u][j];38 ????}39 ????if (u == v) return u;40 ????for (int j=15; j>=0; --j) 41 ????????if (f[u][j] != f[v][j]) 42 ????????????u = f[u][j], v = f[v][j];43 ????return f[u][0];44 }45 46 int main () {47 ????48 ????int n = read(), m = read(), Q = read();49 ????Rep (i, 1, m) {50 ????????e[i].u = read(), e[i].v = read(), e[i].w = read();51 ????}52 ????sort(e+1, e+m+1);53 ????54 ????Rep (i, 1, n+n) fa[i] = i;55 ????CntNode = n;56 ????Rep (i, 1, m) {57 ????????int u = find(e[i].u), v = find(e[i].v);58 ????????if (u == v) continue;59 ????????ch[++CntNode][0] = u; ch[CntNode][1] = v;60 ????????fa[u] = fa[v] = CntNode;61 ????????f[u][0] = f[v][0] = CntNode;62 ????????val[CntNode] = e[i].w;63 ????}64 ????deth[CntNode] = 1;65 ????dfs(CntNode);66 ????67 ????Rep (j, 1, 15)68 ????????Rep (i, 1, n+n)69 ????????????f[i][j] = f[f[i][j-1]][j-1];70 ????Rep (i, 1, Q) {71 ????????int u = read(), v = read();72 ????????int t = Lca(u,v);73 ????????printf("%d\n",val[Lca(u,v)]);74 ????}75 ????76 ????return 0;77 }3732: Network
原文地址：https://www.cnblogs.com/mjtcn/p/9353132.html