hello.

题解 P1967 【货车运输】

2018-02-25 21:47:42


这道题卡了两天,然后在@LDlornd dalao如锋的锐利眼神帮助之下A掉了。

这道题目细节很多,实际上很多题解都是不甚周到的,我自己写的尽量考虑地完整,也有可能有疏忽的地方,多多指教。

思路

看完这道题很容易想到要用最大生成树重构整张图,然后在得到的树上维护两点路径上的最短边权。所以想到用LCA,在寻找最近公共祖先的时候维护一个dim数组,处理路径上的最短边权。

代码

建议在完成本题之前A掉【模板】最近公共祖先,我使用的是倍增方法。

详细的介绍都在注释里了,有疑问请留言QwQ

#include <bits/stdc++.h>
#define INF 0x7777777
#define maxn 500002
using namespace std;
struct Edge{
    int to,next,lim;
    Edge(int x=0,int y=0,int z=0){
        to=x;next=y;lim=z;
    }//一个简单的构造函数
}l[maxn*2];//储存新图的信息
struct Orz{
    int from,to,lim;
    bool operator < (const Orz y) const{
        if (lim==y.lim) return from<y.from;
        return lim>y.lim;
    }//重载运算符,按边权排序,使用Kruskal生成最大生成树
    Orz(int x=0,int y=0,int z=0) {
        from=x;to=y;lim=z;
    }
}ori[maxn*2];//储存题目给定的图信息
int head[maxn],cnt,fa[maxn]; bool seaed[maxn];
int d[maxn],p[18][maxn],dim[18][maxn],n,m;
void add(int x,int y,int z) {
    l[++cnt]=Edge(y,head[x],z);
    head[x]=cnt;
}//前向星建图
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    if (find(x)!=find(y)) fa[find(y)]=find(x);
}//以上并查集基本操作,用于Kruskal以及判定是否可以到达
void Build_Graph(){
    memset(dim,INF,sizeof(dim));
    for (int i=1;i<=n;i++) fa[i]=i;
    sort(ori+1,ori+1+m);
    for (int i=1;i<=m;i++)
        if (find(ori[i].from)!=find(ori[i].to)){
            merge(ori[i].from,ori[i].to);
            add(ori[i].from,ori[i].to,ori[i].lim);
            add(ori[i].to,ori[i].from,ori[i].lim);
        }
}//最大生成树,可能生成了多个树
void dfs(int u,int fa){
    seaed[u]=1;//标记为已搜索
    d[u]=d[fa]+1;
    p[0][u]=fa;
    for (int i=1;(1<<i)<=d[u];i++){
        p[i][u]=p[i-1][p[i-1][u]];
        dim[i][u]=min(dim[i-1][u],dim[i-1][p[i-1][u]]);
    }//更新父节点信息的同时更新路径上的最小边权
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v!=fa){
            dim[0][v]=l[i].lim;
            dfs(v, u);
        }
    }
}//以上标准的倍增LCA预处理过程
int lca(int a,int b){
    int res=INF;
    if (find(a)!=find(b)) return -1;//判读是否联通
    if (d[a]>d[b]) swap(a,b);
    for (int i=16;i>=0;i--)
        if (d[p[i][b]]>=d[a]) res=min(res,dim[i][b]),b=p[i][b];//使a,b上升到同一高度,b向上跳的时候不断更新答案
    if (a==b) return res;
    for (int i=16;i>=0;i--){
        if (p[i][b]==p[i][a]) continue;
        res=min(res,min(dim[i][b],dim[i][a]));//向上跳的时候不断更新答案
        a=p[i][a],b=p[i][b];
    }
    return min(res,min(dim[0][a],dim[0][b]));
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m; int x,y,z,q;
    for (int i=1;i<=m;i++)
    cin>>x>>y>>z,ori[i]=Orz(x,y,z);
    Build_Graph();
    for (int i=1;i<=n;i++)
        if (!seaed[i]) dfs(i,0);//保证可能的所有生成树都被并且处理过一次
    cin>>q;
    while (q--){
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}