题目描述
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。
因为每次要尽量走大的边，所以可以求出来最大生成树，然后在树上倍增求两点之间最小边权即可。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct edge { int x,y,w; bool operator < (const edge & eee) const { return w>eee.w; } }a[50010]; int dep[10010],db_min[10010][17],db_to[10010][17],fir[10010],ne[20010],to[20010],w[20010],fa[10010],tot; bool vis[10010]; void add(int f,int t,int l) { ne[++tot]=fir[f]; fir[f]=tot; to[tot]=t; w[tot]=l; } int find(int x) { if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x]; } void dfs(int u,int fa) { int i,j,k,v; for (i=fir[u];i;i=ne[i]) if (to[i]!=fa) { v=to[i]; db_to[v][0]=u; db_min[v][0]=w[i]; dep[v]=dep[u]+1; dfs(v,u); } } int main() { int i,j,k,m,n,p,q,x,y,z,ans,tem; scanf("%d%d",&n,&m); for (i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); sort(a+1,a+m+1); for (i=1;i<=n;i++) fa[i]=i; for (i=1;i<=m;i++) if (find(a[i].x)!=find(a[i].y)) { fa[fa[a[i].x]]=fa[a[i].y]; add(a[i].x,a[i].y,a[i].w); add(a[i].y,a[i].x,a[i].w); } for (i=1;i<=n;i++) if (!vis[find(i)]) { vis[fa[i]]=1; dep[fa[i]]=0; dfs(fa[i],-1); } for (k=1;k<=15;k++) for (i=1;i<=n;i++) { db_to[i][k]=db_to[db_to[i][k-1]][k-1]; db_min[i][k]=min(db_min[i][k-1],db_min[db_to[i][k-1]][k-1]); } scanf("%d",&q); for (i=1;i<=q;i++) { scanf("%d%d",&x,&y); if (find(x)!=find(y)) { printf("-1\n"); continue; } ans=0x3f3f3f3f; if (dep[y]>dep[x]) { tem=y; y=x; x=tem; } for (k=15;dep[x]>dep[y];k--) if (dep[x]-(1<<k)>=dep[y]) { ans=min(ans,db_min[x][k]); x=db_to[x][k]; } if (x==y) { printf("%d\n",ans); continue; } for (k=15;k>=0;k--) if (db_to[x][k]!=db_to[y][k]) { ans=min(ans,min(db_min[x][k],db_min[y][k])); x=db_to[x][k]; y=db_to[y][k]; } ans=min(ans,min(db_min[x][0],db_min[y][0])); printf("%d\n",ans); } }