这道题不就是Noip2013的t3吗…没想到bzoj换了个包装.noip2013货车运输是最大生成树，这里是最小生成树. 因为要是最大的边最小，则一定存在于最小生成树中.我们只需要跑一遍kruskal再树上倍增求LCA的同时求最大值即可.
注意：代码中Min其实求的是最大值，因为我直接从之前noip2013粘过来的，所以这里偷懒一下只改一下符号没改名称.
#include<stdio.h> #include<algorithm> const int maxn=100001; const int Uplimit=16; int aa,bb,tot,num,ans,h[maxn],fa[maxn],anc[maxn][Uplimit],vmin[maxn][Uplimit],n,m,dep[maxn],q; inline int Min(int x,int y){ return x>y?x:y;} struct optimus{ int x,y,z; }prime[maxn]; struct edge{ int nxt,v,w; }e[maxn*2]; inline void add(int u,int v,int w){ e[++num].v=v,e[num].w=w,e[num].nxt=h[u],h[u]=num; e[++num].v=u,e[num].w=w,e[num].nxt=h[v],h[v]=num; } inline bool cmp(optimus a,optimus b){return a.z<b.z;} inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ register int x=0; register char ch=nc(); while(ch<'0'||ch>'9')ch=nc(); while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=nc(); return x; } int I_Just_Wanna_Run(int x){return x==fa[x]?x:fa[x]=I_Just_Wanna_Run(fa[x]);} inline void kruskal(){ std::sort(prime+1,prime+m+1,cmp); for(register int i=1;i<=n;i++) fa[i]=i; for(register int i=1;i<=m;i++){ aa=I_Just_Wanna_Run(prime[i].x),bb=I_Just_Wanna_Run(prime[i].y); if(aa!=bb){ ++tot; fa[aa]=bb; add(prime[i].x,prime[i].y,prime[i].z); if(tot==n-1) break; } } } void dfs(int u,int father,int value){ dep[u]=dep[father]+1; anc[u][0]=father,vmin[u][0]=value; for(int p=1;p<Uplimit;p++) anc[u][p]=anc[anc[u][p-1]][p-1],vmin[u][p]=Min(vmin[u][p-1],vmin[anc[u][p-1]][p-1]); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].v; if(v==father) continue; dfs(v,u,e[i].w); } } int query(int u,int v){ ans=0; if(dep[u]<dep[v]) std::swap(u,v); int D_depth=dep[u]-dep[v]; for(int p=0;D_depth;D_depth>>=1,p++) if(D_depth&1)ans=Min(ans,vmin[u][p]),u=anc[u][p]; if(u==v) return ans; for(int p=Uplimit-1;p>=0;p--) if(anc[u][p]!=anc[v][p]) ans=Min(ans,Min(vmin[u][p],vmin[v][p])),u=anc[u][p],v=anc[v][p]; return ans=Min(ans,Min(vmin[u][0],vmin[v][0])); } int main(){ n=read(),m=read();q=read(); for(register int i=1;i<=m;i++) prime[i].x=read(),prime[i].y=read(),prime[i].z=read(); kruskal(); for(register int i=1;i<=n;i++) if(!dep[i]) dfs(i,i,0); while(q--){ int x=read(),y=read(); if(I_Just_Wanna_Run(x)!=I_Just_Wanna_Run(y)) printf("-1\n"); else printf("%d\n",query(x,y)); } return 0; }