洛谷 P1967 货车运输

题目描述

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：

输出样例#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

题目链接

#include <algorithm>
#include <cstdio>
#define N 50005

using namespace std;
bool vis[N];
int n,m,cnt,Fa[N],fa[N],dis[N],dep[N],to[N<<1],head[N],nxt[N<<1],val[N<<1];
void dfs(int x,int pr)
{
    vis[x]=true;
    fa[x]=pr;
    dep[x]=dep[pr]+1;
    for(int i=head[x];i;i=nxt[i])
    {
        int v=to[i];
        if(vis[v]) continue;
        dis[v]=val[i];
        dfs(v,x);
    }
}
int solve(int u,int v)
{
    int ret=0x7fffffff,ret2=0x7fffffff;
    if(dep[u]<dep[v]) swap(u,v);
    for(;dep[u]>dep[v];u=fa[u]) ret=min(ret,dis[u]);
    if(u==v) return ret;
    for(;u!=v;u=fa[u],v=fa[v]) ret=min(ret,dis[u]),ret2=min(ret2,dis[v]);
    return min(ret,ret2);
}
struct node
{
    int x,y,z;
    bool operator <(node a)const {return z>a.z;}
}e[N];
int find_(int x) {return x==Fa[x]?x:Fa[x]=find_(Fa[x]);}
void krus()
{
    for(int i=1;i<=n;++i) Fa[i]=i;
    sort(e+1,e+1+m);
    int num=0;
    for(int i=1;i<=m;++i)
    {
        int fx=find_(e[i].x),fy=find_(e[i].y);
        if(fx==fy) continue;
        Fa[fy]=fx;
        nxt[++cnt]=head[e[i].x];to[cnt]=e[i].y;val[cnt]=e[i].z;head[e[i].x]=cnt;
        nxt[++cnt]=head[e[i].y];to[cnt]=e[i].x;val[cnt]=e[i].z;head[e[i].y]=cnt;
        if(++num==n-1) break;
    }
}
int main(int argc,char *argv[])
{
    scanf("%d%d",&n,&m);
    for(int u,v,w,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[i]=(node) {u,v,w};
    }
    krus();
    for(int i=1;i<=n;++i)
     if(!vis[i]) dfs(i,0);
    scanf("%d",&m);
    for(int u,v;m--;)
    {
        scanf("%d%d",&u,&v);
        if(find_(u)!=find_(v)) puts("-1");
        else printf("%d
",solve(u,v));
    }
    return 0;
}