A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道
路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出格式：输出文件名为 truck.out。
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货
车不能到达目的地，输出-1。
对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000； 对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000； 对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。
思路：原图有很多边，有的是没有贡献的，我们的目的是求出点到点的最大可行运输重量，如果x->y有1，2，3，4，5的边，那么只有5的边最优，其他边是没有用的，所以我们可以先求出这个图的最大生成树（克鲁斯卡尔）。
然后如果点到点不可达，在克鲁斯卡尔算法执行时使用的并查集可以迅速判断这一点。现在只需要考虑可达的情况，即给一棵树，求点到点的 路径上的最小边权值。
大部分题解写的是树上倍增，我第一眼写成了树链剖分2333（都怪这个要求太像树链剖分了
唯一要注意的点是：原图可能不是一棵树，而是森林，所以我们应该对每颗树都做一次树链剖分(一开始没注意到竟然只WA了一个点！感谢良心CCF数据制造商，总复杂度O(m+qlog^2(n));
#include<bits/stdc++.h> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define debug(x) cout<<#x<<"="<<x<<endl using namespace std; const int maxn = 10010; struct bian { int from,to; int val; }a[maxn*5]; int f[maxn]; int fa[maxn],dep[maxn],top[maxn],cost[maxn]; int siz[maxn],son[maxn],pos[maxn]; int first[maxn]; bool vis[maxn]; struct edg { int next,val,to; }e[maxn*10]; struct sg_tree { int minn; }node[maxn<<2]; int e_sum; int cnt; int n,m; int q; void updata(int rt) { node[rt].minn=min(node[rt<<1].minn,node[rt<<1|1].minn); } int query(int l,int r,int rt,int left,int right) { if(left<=l&&r<=right) return node[rt].minn; int mid=(l+r)>>1; if(right<=mid) return query(lson,left,right); else if(left>mid) return query(rson,left,right); else return min(query(lson,left,mid),query(rson,mid+1,right)); } void init() { for(int i=1;i<=n;i++) f[i]=i; memset(cost,63,sizeof cost); } bool cmp(bian x,bian y) { return x.val>y.val; } void add_edg(int x,int y,int z) { e_sum++; e[e_sum].next=first[x]; first[x]=e_sum; e[e_sum].to=y; e[e_sum].val=z; } int find(int x) { if(f[x]==x) return x; return f[x]=find(f[x]); } void merge(int x,int y) { f[x]=y; } void dfs1(int x,int ff,int dd) { vis[x]=1; fa[x]=ff; siz[x]=1; dep[x]=dd; for(int i=first[x];i;i=e[i].next) { int w=e[i].to; if(w==ff) continue; cost[w]=e[i].val; dfs1(w,x,dd+1); siz[x]+=siz[w]; if(siz[w]>siz[son[x]]) son[x]=w; } } void dfs2(int x,int ff,int tt) { top[x]=tt; if(x!=1) pos[x]=++cnt; if(son[x]) dfs2(son[x],x,top[x]); for(int i=first[x];i;i=e[i].next) { int w=e[i].to; if(w==ff||w==son[x]) continue; dfs2(w,x,w); } } void insert(int l,int r,int rt,int p,int v) { if(l==r) { node[rt].minn=v; return ; } int mid=(l+r)>>1; if(p<=mid) insert(lson,p,v); else insert(rson,p,v); updata(rt); } int solve(int x,int y) { int xf=top[x],yf=top[y]; int mm=0x3f3f3f3f; while(xf!=yf) { if(dep[xf]<dep[yf]) swap(x,y),swap(xf,yf); mm=min(mm,query(1,cnt,1,pos[xf],pos[x])); x=fa[xf];xf=top[x]; } if(x==y) return mm; if(dep[x]<dep[y]) swap(x,y); return min(mm,query(1,cnt,1,pos[son[y]],pos[x])); } int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].val); sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++) { int xf=find(a[i].from); int yf=find(a[i].to); if(xf==yf) continue; merge(xf,yf); add_edg(a[i].from,a[i].to,a[i].val); add_edg(a[i].to,a[i].from,a[i].val); } for(int i=1;i<=n;i++) { if(!vis[i]) { dfs1(i,-1,1); dfs2(i,-1,i); } } for(int i=2;i<=n;i++) insert(1,cnt,1,pos[i],cost[i]); scanf("%d",&q); for(int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); if(find(x)!=find(y)) printf("-1\n"); else printf("%d\n",solve(x,y)); } return 0; }
