问题 C: 货车运输
时间限制: 1 Sec 内存限制: 128 MB提交: 14 解决: 3
[提交] [状态] [讨论版] [命题人:admin]
题目描述
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入
输入第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市 运输货物到 y 城市，注意：x 不等于 y。
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。
输出
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
样例输入
复制样例数据
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出
3
-1
3
Solution：
先用Kruskal求出最大生成树（因为求的是最大的载物量），再套上树上倍增就好了。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include<bits/stdc++.h> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; typedef long long ll; const int mod=99999997; const int maxn=1e5+5; template <class T> inline void rd(T &ret){char c;ret = 0;while ((c = getchar()) < '0' || c > '9');while (c >= '0' && c <= '9'){ret = ret * 10 + (c - '0'), c = getchar();} } struct node{int x,y,w;bool operator>(const node& tmp)const{return w>tmp.w;} }p[maxn]; struct tree{int v,w,nx; }g[maxn]; int n,m,fa[maxn][20],d[maxn][20],tot,f[maxn],depth[maxn],vis[maxn],head[maxn]; void addedge(int u,int v,int w){g[++tot].v=v,g[tot].w=w,g[tot].nx=head[u],head[u]=tot; } int fd(int now){if(now==f[now])return now;else{return fd(f[now]);} } void dfs(int x){vis[x]=1;REP(i,1,16){if(depth[x]<(1<<i))break;fa[x][i]=fa[fa[x][i-1]][i-1];d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);}for(int i=head[x];i;i=g[i].nx){if(vis[g[i].v])continue;fa[g[i].v][0]=x;depth[g[i].v]=depth[x]+1;d[g[i].v][0]=g[i].w;dfs(g[i].v);} } int lca(int x,int y){if(depth[x]<depth[y])swap(x,y);int len=depth[x]-depth[y];REP(i,0,16){if((1<<i)&len)x=fa[x][i];}PER(i,16,0){if(fa[x][i]!=fa[y][i]){x=fa[x][i],y=fa[y][i];}}if(x==y)return x;else return fa[x][0]; } int qy(int x,int ft){int ans=0x3f3f3f3f;int len=depth[x]-depth[ft];REP(i,0,16){if(len&(1<<i)){ans=min(ans,d[x][i]);x=fa[x][i];}}return ans; } bool cmp(node x,node y){return x.w>y.w;} int main(){rd(n),rd(m);memset(d,127,sizeof(d));REP(i,1,n)f[i]=i;REP(i,1,m)rd(p[i].x),rd(p[i].y),rd(p[i].w);sort(p+1,p+1+m,cmp);int lr=0;REP(i,1,m){int fx=fd(p[i].x),fy=fd(p[i].y);if(fx!=fy){f[fx]=fy;addedge(p[i].x,p[i].y,p[i].w);addedge(p[i].y,p[i].x,p[i].w);lr++;if(lr==n-1)break;}}REP(i,1,n)if(!vis[i])dfs(i);int query;rd(query);REP(i,1,query){int s,t;rd(s),rd(t);if(fd(s)!=fd(t))cout<<-1<<endl;else{int gt=lca(s,t);cout<<min(qy(s,gt),qy(t,gt))<<endl;}} }
