题解 Luogu P1967 货车运输

作者: MayFlyyh 分类: LCA, 倍增 发布时间: 2018-02-24 17:43 ė 6 没有评论

题解 Luogu P1967 货车运输

题目描述

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。

对于 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。

分析:从A点到B点,所运输最重的货物为道路中承重最小的道路的承重值
(有二分的意思)

### 1.求图的最大生成树
故从A运输到B,需要找到从A点到B点的途径中尽量大的道路,而当中的最小道路即是最大承重量

由一个点能到达所有点,想到了图的生成树,便要求该图的最大生成树

解释:A B C三个点互相连接,1.A至B承重10 2.B至C承重20 3.A至C承重5

那么A至C的最大承重是5吗?不是,是10,为A至B,B至C中的最大承重

至于A至C这个边,我们便可以舍去了

### 2.求两点的最近公共祖先

既然求了最大生成树,那么整个图就简化成一颗树的形式了,那么A和B的最大承重就是 A到A与B的最近公共祖先 与B到A与B的最近公共祖先 的最大承重的最小值,那么意味着我们将要 以某点为根,求该最大生成树各自的公共祖先(代码中使用倍增法求)

### 3.倍增法求与各个祖先的最大承重

求到了各自的最近公共祖先,可以采用记忆化搜索DFS一遍该点到祖先的最大承重
也可以采用倍增的思想;

代码实现:

#include<bits/stdc++.h>
#define N 10000+100
#define M 1000000
#define inf 999999999+1
int D[N],f[N],F[N][20],cnt=0,V[N],Ans[N][20];
int LCAO;
int last[N],log2n;
int n,m,q,p,x,y;
struct edge1{
    int from,to,v;
    bool operator < (const edge1 &m) const {
        return v>m.v;
    }
}a[M];
struct edge2{
    int to,next,v;
}e[M*2+1];
inline void add(int x,int y,int z){
    cnt++;e[cnt].next=last[x],last[x]=cnt;e[cnt].to=y,e[cnt].v=z;
    cnt++;e[cnt].next=last[y],last[y]=cnt;e[cnt].to=x,e[cnt].v=z;
}
int find(int x){
    return f[x]==x ? x:f[x]=find(f[x]);
}
inline int merge(int x,int y){
    int t1=find(x),t2=find(y);
    if(t1==t2) return 0;
    f[t1]=t2;
    return 1;
}
void Kr(){
    std::sort(a+1,a+m+1);
    int cnt=0;
    for(int i=1;i<=m;++i){
        if(merge(a[i].from,a[i].to)){
            cnt++;
            add(a[i].from,a[i].to,a[i].v);
        }
        if(cnt==n-1) return;
    }
}
void DFS(int x,int fa){
    V[x]=1;
    D[x]=D[fa]+1;
    F[x][0]=fa;

    for(int i=last[x];i;i=e[i].next){
        if(V[e[i].to]) continue;
        Ans[e[i].to][0]=e[i].v;
        DFS(e[i].to,x);
    }
}
void BZ(){
    for(int i=1;i<=log2n;++i){
        for(int j=1;j<=n;++j){
            if(D[j]>=(1<<i)){
                F[j][i]=F[F[j][i-1]][i-1];
                Ans[j][i]=std::min(Ans[F[j][i-1]][i-1],Ans[j][i-1]);
            }
        }
    }
}
int LCA(int x,int y){
    if(D[x]<D[y]) std::swap(x,y);
    for(int j=log2n;j>=0;--j){
        if(D[F[x][j]]>=D[y])
            x=F[x][j];
    }
    if(x==y) return x;
    for(int j=log2n;j>=0;--j){
        if(F[x][j]!=F[y][j])
            x=F[x][j],y=F[y][j];
    }
    return F[x][0];
}
int QUDIS(int x,int y){
    //if(x==y) return 0;
    int ans=inf;
    int s=0;
    for(int j=log2n;j>=0;--j){
        if(D[F[x][j]]>=D[y]){
            if(F[x][j]!=0)
                ans=std::min(ans,Ans[x][j]);
            x=F[x][j];

        }
    }
    return ans;
}
int Qu(int x,int y){
    int LCAO=LCA(x,y);
    int disx=QUDIS(x,LCAO),disy=QUDIS(y,LCAO);
    int ans=std::min(disx,disy);
    return ans;
}
int main (){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d %d %d",&a[i].from,&a[i].to,&a[i].v);
    log2n=log((n-1)*1.0)/log(2.0)+0.5;
    for(int i=1;i<=n;++i)
        f[i]=i;
    Kr();
    DFS(1,0);
    BZ();
    int Q;
    scanf("%d",&Q);
    for(int i=1;i<=Q;++i){
        scanf("%d %d",&q,&p);
        int ans=Qu(q,p);
        if(ans==inf) ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/59

发表评论

电子邮件地址不会被公开。

Ɣ回顶部