题目描述 Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 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 Description
输出共有 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
数据范围及提示 Data Size & Hint
对于 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。
/* 最大生成树+LCA维护最小值 并查集忘记打return了，找了一晚上的错误 */ #include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<algorithm> #define M 50010 #define S 20 #define INF 0x3f3f3f3f using namespace std; int deep[M],father[M],fa[M][S+5],dis[M][S+5],n,m; vector<int> grap[M]; vector<int> quan[M]; struct node { int l,r,v; };node e[M*2]; int cmp(const node&x,const node&y) { return x.v>y.v; } int find(int x) { if(father[x]==x)return x; else return father[x]=find(father[x]); } void dfs(int now,int from,int c,int w) { fa[now][0]=from;deep[now]=c;dis[now][0]=w; for(int i=0;i<grap[now].size();i++) { int j=grap[now][i]; if(from!=j) dfs(j,now,c+1,quan[now][i]); } } void get_fa() { for(int j=1;j<=S;j++) for(int i=1;i<=n;i++) { fa[i][j]=fa[fa[i][j-1]][j-1]; dis[i][j]=min(dis[i][j-1],dis[fa[i][j-1]][j-1]); } } int LCA(int a,int b) { if(deep[a]<deep[b])swap(a,b); int t=deep[a]-deep[b],ans=INF; if(t) { for(int i=0;i<=S;i++) if(t&(1<<i)) { ans=min(ans,dis[a][i]); a=fa[a][i]; } } if(a==b)return ans; for(int i=S;i>=0;i--) if(fa[a][i]!=fa[b][i]) { ans=min(ans,dis[a][i]); ans=min(ans,dis[b][i]); a=fa[a][i]; b=fa[b][i]; } ans=min(ans,min(dis[a][0],dis[b][0])); return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].v); sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++) { int a=find(e[i].l); int b=find(e[i].r); if(a!=b) { father[b]=a; grap[e[i].l].push_back(e[i].r); grap[e[i].r].push_back(e[i].l); quan[e[i].l].push_back(e[i].v); quan[e[i].r].push_back(e[i].v); } } memset(dis,INF,sizeof(dis)); dfs(1,1,0,0);dis[1][0]=INF;get_fa(); int p; scanf("%d",&p); for(int i=1;i<=p;i++) { int x,y; scanf("%d%d",&x,&y); if(find(x)!=find(y))printf("-1 "); else printf("%d ",LCA(x,y)); } return 0; }