Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
Input
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
Output
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
Sample Output
3
-1
3
Hint
对于 30%的数据，0 ＜ n ＜1,000，0 ＜ m ＜ 10,000，0 ＜ q ＜ 1,000；
对于 100%的数据，0 ＜ n ＜ 10,000，0 ＜ m ＜ 50,000，0 ＜ q ＜ 30,000，0 ≤ z ≤ 100,000。
题解：
这个题目是找每条路径上的最大边权的最小最大值，首先要知道结论，图中任意两点路径的最大最小值一定是在这个图的最大生成树上，因为我们做克鲁斯卡尔的时候，是将边从大到到小排序，然后一颗生成树包含了图中任意节点并且因为是从大到小，所以所以的边都尽量选最大的，那么限制条件——那个最小值一定在树上，所以把树扣出来，用倍增或者是树链剖分维护一下就可以了。主要对森林的处理，用并查集维护同时向一个联通块连一条-1的边。
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> const int MAXN=200300; using namespace std; int n,m,q,num=0,faa[MAXN]; struct edge1{ int from,to,quan; void read(){ scanf("%d%d%d",&from,&to,&quan); } }e[MAXN*2]; struct edge3{ int from,to,quan; }h[MAXN*2]; struct edge{ int to,quan,first,next; }a[MAXN*2]; int son[MAXN],size[MAXN],deep[MAXN],fa[MAXN]; int top[MAXN],id[MAXN],w[MAXN],numm; struct tree{ int l,r,minn; }tr[MAXN*4]; void cl(){ for(int i=1;i<=MAXN*4-1;i++) tr[i].minn=1<<30; memset(fa,0,sizeof(fa)); memset(son,0,sizeof(son)); memset(size,0,sizeof(size)); memset(deep,0,sizeof(deep)); memset(top,0,sizeof(top)); memset(id,0,sizeof(id)); memset(w,0,sizeof(w)); } bool comp(edge1 x,edge1 y){ if(x.quan>y.quan) return 1; return 0; } void addedge(int from,int to,int quan){ a[++num].to=to; a[num].quan=quan; a[num].next=a[from].first; a[from].first=num; } int find(int now){ if(now!=faa[now]) faa[now]=find(faa[now]); return faa[now]; } void hebin(int x,int y){ int hh=find(x),hhh=find(y); faa[hh]=hhh; } void Mtree(){ for(int i=1;i<=m;i++) e[i].read(); for(int i=1;i<=n;i++) faa[i]=i; for(int i=1;i<=m;i++){ int x=e[i].from,y=e[i].to; if(find(x)!=find(y)){ hebin(x,y); } } for(int i=2;i<=n;i++){ if(find(1)!=find(i)){ int hh=find(1),yy=find(i); e[++m].from=hh,e[m].to=yy,e[m].quan=-1; hebin(hh,yy); } } sort(e+1,e+m+1,comp); for(int i=1;i<=n;i++) faa[i]=i;numm=0; for(int i=1;i<=m;i++){ int x=e[i].from,y=e[i].to,z=e[i].quan; int xx=find(x); int yy=find(y); if(xx!=yy){ numm++; hebin(x,y); addedge(x,y,z),addedge(y,x,z); h[numm].from=x,h[numm].to=y,h[numm].quan=z; } if(numm==n-1) break; } } void dfs1(int now,int f){ fa[now]=f; size[now]=1; deep[now]=deep[f]+1; for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; if(to==f) continue; dfs1(to,now); size[now]+=size[to]; if(size[son[now]]<size[to]) son[now]=to; } } void dfs2(int now,int rf){ top[now]=rf; id[now]=++num; if(son[now]) dfs2(son[now],rf); for(int i=a[now].first;i;i=a[i].next){ int to=a[i].to; if(to==fa[now]||to==son[now]) continue; dfs2(to,to); } } void build(int xv,int l,int r){ if(l==r){ tr[xv].l=l,tr[xv].r=r; if(l==1) return; tr[xv].minn=w[l]; return; } tr[xv].l=l,tr[xv].r=r; int mid=(l+r)/2; build(xv*2,l,mid); build(xv*2+1,mid+1,r); tr[xv].minn=min(tr[xv*2].minn,tr[xv*2+1].minn); } int kanxun(int xv,int l,int r){ int L=tr[xv].l,R=tr[xv].r,mid=(L+R)/2; if(l==L&&r==R){ return tr[xv].minn; } if(r<=mid) return kanxun(xv*2,l,r); else if(l>mid) return kanxun(xv*2+1,l,r); else return min(kanxun(xv*2,l,mid),kanxun(xv*2+1,mid+1,r)); } int getmin(int x,int y){ int topx=top[x],topy=top[y],minn=1<<30; while(topx!=topy){ if(deep[topx]<deep[topy]) swap(x,y),swap(topx,topy); minn=min(kanxun(1,id[topx],id[x]),minn); x=fa[topx],topx=top[x]; } if(x==y) return minn; if(deep[x]<deep[y]) swap(x,y); minn=min(minn,kanxun(1,id[son[y]],id[x])); return minn; } int main(){ cl(); scanf("%d%d",&n,&m); Mtree(); memset(fa,0,sizeof(fa)); dfs1(1,0); num=0; dfs2(1,1); for(int i=1;i<=numm;i++){ if(deep[h[i].from]>deep[h[i].to]) swap(h[i].from,h[i].to); int to=h[i].to,quan=h[i].quan; w[id[to]]=quan; } build(1,1,num); scanf("%d",&q); for(int i=1;i<=q;i++){ int x,y; scanf("%d%d",&x,&y); printf("%d ",getmin(x,y)); } }