传送门
一辆车的载重，取决于他到终点上的路的载重最小值，最小值越大，装的就越多
考虑如何找路径，如果bfs或者dfs的话，TLE。
这时想到，我们可以做一颗最大生成树（按照权值从大到小排序），在生成树的基础上，两点之间都是联通的，而且载重也是最优的。
这时考虑如何在生成树上找到两点的路径，一棵树，自然而然地就想到了LCA，然后就AC了。
#include<bits/stdc++.h> #define N 10005 #define M 50005 using namespace std; int n,m,father[N],tot,first[N],dep[N],up[N][22],w[N][22]; const int INF=0x7fffffff; struct A { int from,to,val; }a[M]; struct node { int to,next,val; }edge[2*M]; inline int getfather(int x) { if(father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } inline void addedge(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].next=first[x]; edge[tot].val=z; first[x]=tot; } inline bool cmp(const A &x,const A &y) { return x.val>y.val; } void Init() { for(int i=1;i<=n;i++) { father[i]=i; } } void kruskal() { int k=0; for(int i=1;i<=m;i++) { int x=a[i].from; int y=a[i].to; int ax=getfather(x); int bx=getfather(y); if(ax!=bx) { father[ax]=bx; k++; addedge(x,y,a[i].val); addedge(y,x,a[i].val); } if(k==n-1) break; } } inline void dfs(int now) { for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(dep[vis]) continue; dep[vis]=dep[now]+1; up[vis][0]=now; w[vis][0]=edge[u].val; dfs(vis); } } inline int lca(int x,int y) { if(getfather(x)!=getfather(y)) return -1; if(dep[x]<dep[y]) swap(x,y); int ans=INF; for(int i=20;i>=0;i--)//注意是到0，而不是1，是1就WA了 { if(dep[up[x][i]]>=dep[y]) { ans=min(ans,w[x][i]); x=up[x][i]; } } if(x==y) return ans; for(int i=20;i>=0;i--) { if(up[x][i]!=up[y][i]) { ans=min(ans,min(w[x][i],w[y][i])); x=up[x][i]; y=up[y][i]; } } ans=min(ans,min(w[x][0],w[y][0])); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; Init(); for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; a[i].from=x,a[i].to=y,a[i].val=z; } sort(a+1,a+m+1,cmp); kruskal(); for(int i=1;i<=n;i++)//由于不确定生成树包含哪些点 所以要一个一个扫描 { if(!dep[i]) { dep[i]=1; dfs(i); up[i][0]=i; w[i][0]=INF; } } for(int j=1;j<=20;j++) { for(int i=1;i<=n;i++) { up[i][j]=up[up[i][j-1]][j-1]; w[i][j]=min(w[i][j-1],w[up[i][j-1]][j-1]); } } int q; cin>>q; for(int i=1;i<=q;i++) { int x,y; cin>>x>>y; cout<<lca(x,y)<<'\n'; } return 0; }