货车运输

A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入描述:

第一行有两个用一个空格隔开的整数n,m，表示 A国有n座城市和m条道路。
接下来m行每行3个整数x,y,z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。注意：x不等于y，两座城市之间可能有多条道路。
接下来一行有一个整数q，表示有q辆货车需要运货。
接下来q行，每行两个整数x y，之间用一个空格隔开，表示一辆货车需要从x城市运输货物到y城市，注意：x不等于y。

输出描述:

共有q行，每行一个整数，表示对于每一辆货车，它的最大载重可以是多少。如果货车不能到达目的地，输出-1。

示例1
输入

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出

3
-1
3

说明

n,m,q<=10^4, z<=10^5

huocheyunshu.cppview raw

#include<stdio.h>
#include<string.h>
#include<vector>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#define M 100005
#define oo 2000000000
using namespace std;
struct node{
    int x,y,z;
}s[M];
struct Query{
    int x,id,next;
}query[M*10];
void Rd(int &res){
    char c;res=0;
    while(c=getchar(),!isdigit(c));
    do{
        res=(res<<3)+(res<<1)+(c^48);
    }while(c=getchar(),isdigit(c));
}
int fa[M],ans[M];
int qcnt[M],head[M],tot=0;
int get(int v){
    if(fa[v]!=v)
        fa[v]=get(fa[v]);
    return fa[v];
}
bool cmp(node A,node B){
    return A.z>B.z;
}
void check(int &x,int y){
    if(x<y)x=y;
}
void add(int a,int b,int c){
    qcnt[a]++;
    query[tot].x=b,query[tot].id=c,query[tot].next=head[a],head[a]=tot++;
}
int main(){
    int n,m,q,x,y,i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)fa[i]=i;
    for(i=0;i<m;i++){
        Rd(s[i].x);Rd(s[i].y);Rd(s[i].z);
    }
    sort(s,s+m,cmp);
    Rd(q);
    memset(head,-1,sizeof(head));
    for(i=0;i<q;i++){
        Rd(x);Rd(y);
        add(x,y,i);add(y,x,i); ans[i]=-1;
    }
    for(i=0;i<m;i++){
        x=s[i].x,y=s[i].y;
        int fx=get(x),fy=get(y);
        if(fx==fy)continue;
        if(qcnt[fx]>qcnt[fy])swap(fx,fy);
        fa[fx]=fy;
        for(j=head[fx];j!=-1;j=query[j].next){
            if(get(query[j].x)==fy)check(ans[query[j].id],s[i].z);
            else add(fy,query[j].x,query[j].id);
        }
    }
    for(i=0;i<q;i++)printf("%d\n",ans[i]);
    return 0;
}