stonechina0616

题目描述

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;

}