Luogu货车运输

2017-08-04

货车运输

题目描述

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。

思路：

最大生成树+lca

首先可以用最大生成树get一只树，显然，沿着树上的路径的路径走一定是最小值最大的

树上路径自然就是lca了，这（只）里（会）倍增，除了倍增用的祖先还统计了路径上的最小值（一个s一个t），然后查询lca顺带维护一个最小值就好了

#include<algorithm>
#include<iostream>
#include<cstdio>
#define N 10010
#define M 50010*4
#define inf 1<<30
using namespace std;
struct eage
{
    int u,v,l;
}a[M];
bool comp(eage aa,eage bb)
{
    return aa.l>bb.l;
}
int e,n,m,q,t[N][20],s[N][20];
int dep[N],f[N],num[N],head[N],to[M],next[M],len[M];
int get_f(int now)
{
    if(now==f[now]) return f[now];
    else return f[now]=get_f(f[now]);
}
void buid(int u,int v,int l)
{
    next[++e]=head[u],head[u]=e;
    to[e]=v,len[e]=l;
}
void join(int u,int v)
{
    if(num[u]>num[v]) swap(u,v);
    f[u]=f[v];
    num[v]+=num[u];
}
void dfs(int now,int fa,int l,int dp)
{
    dep[now]=dp;
    s[now][0]=fa;
    t[now][0]=l;
    for(int i=head[now];i;i=next[i])
    {
        int j=to[i];
        if(j!=fa)
        {
            dfs(j,now,len[i],dp+1);
        }
    }
}
void do_st()
{
    for(int j=1;j<=15;j++)
        for(int i=1;i<=n;i++)
            s[i][j]=s[s[i][j-1]][j-1];
    for(int j=1;j<=15;j++)
        for(int i=1;i<=n;i++)
            t[i][j]=min(t[i][j-1],t[s[i][j-1]][j-1]);
}
int ask(int u,int v)
{
    int re=inf;
    if(dep[u]<dep[v]) swap(u,v);
    //u>v
    int c=dep[u]-dep[v];
    for(int i=0;i<=15;++i)
    {
        if(c&(1<<i))
        {
            re=min(re,t[u][i]);
            u=s[u][i];
        }
    }
    if(u==v) return re;
    for(int i=15;i>=0;i--)
    {
        if(s[u][i]!=s[v][i])
        {
            re=min(t[u][i],re);
            re=min(t[v][i],re);
            u=s[u][i];
            v=s[v][i];
        }
    }
    re=min(t[u][0],re);
    re=min(t[v][0],re);
    return re;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].l);
    }
    sort(a+1,a+m+1,comp);
    for(int i=1;i<=n;++i) f[i]=i,num[i]=1;
    for(int i=1;i<=m;++i)
    {
        int fa=get_f(a[i].u),fb=get_f(a[i].v);
        if(fa==fb) continue;
        join(fa,fb);
        buid(a[i].u,a[i].v,a[i].l);
        buid(a[i].v,a[i].u,a[i].l);
    }
    dfs(1,0,inf,1);
    do_st();
    scanf("%d",&q);
    for(int i=1;i<=q;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(get_f(u)!=get_f(v))
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n",ask(u,v));
    }
    return 0;
}
Comment Box
(update the code to your comment plugin in comment-full.html)