这道题让我们求最小限重的最大值
显然可以先求出最大生成树，然后在树上进行操作
因为如果两点之间有多条路径的话一定会走最大的，而其他小的路径是不会被走的
然后考虑求最小权值
可以采用倍增求LCA，预处理时顺便把最小权值求出来
Code:
1 #include<bits/stdc++.h> 2 #define IO4 10000+10 3 #define debug cout<<"Error"<<endl 4 using namespace std; 5 int n,m,q,cnt,cntt; 6 //原图 7 struct Edge { 8 int from,to,wei; 9 }e[10*IO4]; 10 inline void ade(int u,int v,int w){ 11 e[++cnt].from=u; 12 e[cnt].to=v; 13 e[cnt].wei=w; 14 } 15 inline bool cmp(Edge a,Edge b){ 16 return a.wei>b.wei; 17 } 18 //最大生成树 19 struct Edget { 20 int nextt,tot,weit; 21 }te[2*IO4]; 22 int head[IO4]; 23 inline void adte(int u,int v,int w){ 24 te[++cntt].tot=v; 25 te[cntt].weit=w; 26 te[cntt].nextt=head[u]; 27 head[u]=cntt; 28 } 29 //并查集 30 int fa[IO4]; 31 int fd(int x){ 32 return fa[x]==x?x:fa[x]=fd(fa[x]); 33 } 34 //Kruskal算法 35 inline void Solve_MST(){ 36 int now=0; 37 sort(e+1,e+1+cnt,cmp); 38 for(int i=1;i<=n;i++)fa[i]=i; 39 for(int i=1;i<=cnt;i++){ 40 int u=fd(e[i].from); 41 int v=fd(e[i].to); 42 if(u==v)continue; 43 fa[u]=v; 44 //建新图 45 adte(u,v,e[i].wei); 46 adte(v,u,e[i].wei); 47 now++; 48 if(now==n-1)return; 49 } 50 } 51 //搜索 52 int f[IO4][25],minw[IO4][25],vis[IO4],dep[IO4]; 53 void DFS(int x){ 54 vis[x]=1; 55 for(int i=head[x];i;i=te[i].nextt){ 56 int tot=te[i].tot; 57 if(vis[tot])continue; 58 dep[tot]=dep[x]+1; 59 f[tot][0]=x; 60 //两个直接连接的点之间的最小权值就是这条边 61 minw[tot][0]=te[i].weit; 62 DFS(tot); 63 } 64 } 65 //预处理 66 inline void Init(){ 67 for(int i=1;i<=n;i++){ 68 if(!vis[i]){ 69 DFS(i); 70 f[i][0]=i; 71 minw[i][0]=0x3f3f3f3f; 72 } 73 } 74 for(int l=1;l<=20;l++){ 75 for(int i=1;i<=n;i++){ 76 f[i][l]=f[f[i][l-1]][l-1]; 77 //这里多了一步求最小权值 78 //minw=min(前半minw,后半minw) 79 minw[i][l]=min(minw[i][l-1],minw[f[i][l-1]][l-1]); 80 } 81 } 82 } 83 //倍增求LCA（以下都是常规操作） 84 inline int Solve_LCA(int x,int y){ 85 int ans=0x3f3f3f3f; 86 if(fd(x)!=fd(y))return -1; 87 if(dep[x]<dep[y])swap(x,y); 88 for(int l=20;l>=0;l--){ 89 if(dep[x]-(1<<l)>=dep[y]){ 90 //注意要先取min否则x会改变 91 ans=min(ans,minw[x][l]); 92 x=f[x][l]; 93 } 94 } 95 if(x==y)return ans; 96 for(int l=20;l>=0;l--){ 97 if(f[x][l]!=f[y][l]){ 98 //同上 99 ans=min(ans,min(minw[x][l],minw[y][l])); 100 x=f[x][l],y=f[y][l]; 101 } 102 } 103 //由于跳到LCA下面所以再取一步 104 ans=min(ans,min(minw[x][0],minw[y][0])); 105 return ans; 106 } 107 108 int main(){ 109 ios::sync_with_stdio(0); 110 cin>>n>>m; 111 for(int i=1;i<=m;i++){ 112 int x,y,z; 113 cin>>x>>y>>z; 114 ade(x,y,z); 115 } 116 Solve_MST(); 117 Init(); 118 cin>>q; 119 for(int i=1;i<=q;i++){ 120 int x,y; 121 cin>>x>>y; 122 cout<<Solve_LCA(x,y)<<endl; 123 } 124 return 0;//完结撒花 125 }