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。
输入输出样例输入样例#1:
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
输出样例#1:
3 -1 3
对于 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和一段树上的最小值。
注意:
1.并查集一定要路径压缩;
2.倍增时要求树上的最小值。
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cstring>
#define rep(q,p) for (int q=1;q<=p;q++)
using namespace std;
const int maxn=1e4+5,lognum=14;
int n,m,x,y,z,p[maxn],dis[maxn],r[maxn],que;
int dep[maxn],f[maxn][lognum+2],rq[maxn][lognum+2];
vector<pair<int,int> >v[maxn];
bool vis[maxn];
struct hehe{int xpoint,ypoint,num;}a[maxn*5];
int min(int x,int y)
{
return x>y?y:x;
}
int build(int k)
{
return r[k]==k ? r[k] : r[k]=build(r[k]);
}
void build_road(int k)
{
int tx=build(a[k].xpoint),ty=build(a[k].ypoint);
r[tx]=ty;
v[a[k].xpoint].push_back(make_pair(a[k].num,a[k].ypoint));
v[a[k].ypoint].push_back(make_pair(a[k].num,a[k].xpoint));
}
bool pan(int xx,int yy)
{
return build(xx)==build(yy) ? true : false;
}
bool cmp(hehe t1,hehe t2)
{
return t1.num>t2.num;
}
void kruskal()
{
sort(a+1,a+m+1,cmp);
rep(i,n) r[i]=i;
rep(i,m)
if (build(a[i].xpoint)!=build(a[i].ypoint))
build_road(i);
}
void dfs_lca(int k,int fa,int d)
{
vis[k]=true;
dep[k]=d;
f[k][0]=fa;
for (int i=0;i<v[k].size();i++)
if (v[k][i].second!=fa)
{
rq[v[k][i].second][0]=v[k][i].first;
dfs_lca(v[k][i].second,k,d+1);
}
}
void init_lca()
{
rep(j,lognum) rep(i,n)
f[i][j]=f[f[i][j-1]][j-1],rq[i][j]=min(rq[i][j-1],rq[f[i][j-1]][j-1]);
}
int query(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y],mn=INT_MAX;
if(d>0) for(int i=0; d&&i<=lognum; i++,d>>=1) if(d&1) mn=min(mn,rq[x][i]),x=f[x][i];
if(x==y) return mn;
for(int i=lognum; i>=0; i--) if(f[x][i]!=f[y][i])
mn=min(mn,min(rq[x][i],rq[y][i])),x=f[x][i],y=f[y][i];
mn=min(mn,min(rq[x][0],rq[y][0]));
return mn;
}
int main()
{
freopen("in.txt","r",stdin);
memset(rq,127,sizeof(rq));
scanf("%d%d",&n,&m);
rep(i,m) scanf("%d%d%d",&a[i].xpoint,&a[i].ypoint,&a[i].num);
kruskal();
rep(i,n) if (!vis[i]) dfs_lca(i,0,1);
init_lca();
scanf("%d",&que);
while (que--)
{
int x,y;
scanf("%d%d",&x,&y);
int tx=build(x),ty=build(y);
if (r[tx]==ty) printf("%d\n",query(x,y));
else printf("-1\n");
}
return 0;
}
© stonechina0616 | Powered by LOFTER