P1967 [NOIP2013 提高组] 货车运输 题解

· · 个人记录

P1967 [NOIP2013 提高组] 货车运输 题解

最大生成树+树链剖分

先走一遍Kruskal求最大生成树 生成最大生成树后可以保证每两个点之间路径的最短路径最长

可以简单证明得知：如果存在一条非最大生成树路径中的最短边大于了最大生成树的路径中的最短边

那么这条边在Kruskal遍历的时候会优先作为链接两个森林的边加入最大生成树所以实际上不会存在这样的路径

我们以随机一个点A为根节点 化边权为点权 即将在最大生成树上的从父节点连向子节点的边的权值赋给子节点

之后跑一遍树链剖分打树剖模板

对于每次查询(a,b) 先求出LCA(a,b) 然后遍历LCA的每一条边 求出既是a的祖先又是LCA的子节点的点a1 既是b的祖先又是LCA的子节点的点b1

之后树剖求 a->a1路径的最小值与b->b1路径的最小值的最小值即为答案

下面附上代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 20010
#define MAXM 100010
const int INF=1<<30;
using namespace std;
int Head[MAXN],Total=1,Father[MAXN],Line[MAXN],cnt=0,m,n,Root=1,DFN[MAXN],In1[MAXM],In2[MAXM],In3[MAXM],E[MAXM<<1];
struct L{
    int St,Ed;
    int Next;
    int Value;
    int Mark;
    bool Exist;
}Edge[MAXM<<1];
struct N{
    int Father,Size,Son,Top,Depth,Value;
}Node[MAXN];
void Edge_Add(int St,int Ed,int Value){
    Total++;
    Edge[Total].St=St;
    Edge[Total].Ed=Ed;
    Edge[Total].Next=Head[St];
    Edge[Total].Value=Value;
    Edge[Total].Exist=E[Total];
    Edge[Total].Mark=Total;
    Head[St]=Total;
}
bool cmp(L a,L b){
    return a.Value>b.Value;
}
int Find(int a){
    if(Father[a]==a) return a;
    else{
        Father[a]=Find(Father[a]);
        return Father[a];
    }
}
void Merge(int a,int b){
    Father[Find(a)]=Find(b);
    return;
}
void Kruskal(){//注：实际上跑Kruskal不需要建边，但是我这里是建边跑的所以后面要重建，防止乱序
    int Need=n-1;
    sort(Edge+2,Edge+Total+1,cmp);
    for(int i=1;i<=Total;i++){
        int P1=Edge[i].St,P2=Edge[i].Ed;
        if(Find(P1)!=Find(P2)&&Need!=0){
            Merge(P1,P2);
            E[Edge[i].Mark]=1;
            E[(Edge[i].Mark^1)]=1;
            Need--;
        }
    }
}
void Rebulid(){
    Total=1;
    for(int i=1;i<=m;i++){
        Edge_Add(In1[i],In2[i],In3[i]);
        Edge_Add(In2[i],In1[i],In3[i]);
    }
}
void Give(int Now){
    for(int i=Head[Now];i;i=Edge[i].Next){
        if(Edge[i].Exist&&Edge[i].Ed!=Node[Now].Father){
            Node[Edge[i].Ed].Value=Edge[i].Value;
            Give(Edge[i].Ed);
        }
    }
}
void DFS1(int Now){
    Node[Now].Size=1;
    Node[Now].Son=-1;
    for(int i=Head[Now];i;i=Edge[i].Next){
        if(Edge[i].Ed!=Node[Now].Father&&Edge[i].Exist){
            Node[Edge[i].Ed].Father=Now;
            Node[Edge[i].Ed].Depth=Node[Now].Depth+1;
            DFS1(Edge[i].Ed);
            Node[Now].Size+=Node[Edge[i].Ed].Size;
            if(Node[Now].Son==-1){Node[Now].Son=Edge[i].Ed;}
            else if(Node[Edge[i].Ed].Size>Node[Node[Now].Son].Size){Node[Now].Son=Edge[i].Ed;}
        }
    }
    if(Node[Now].Son==-1) Node[Now].Son=Now;
}
void DFS2(int Now){
    cnt++;
    DFN[Now]=cnt;
    Line[cnt]=Node[Now].Value;
    if(Node[Now].Son!=Now){
        Node[Node[Now].Son].Top=Node[Now].Top;
        DFS2(Node[Now].Son);
    }
    for(int i=Head[Now];i;i=Edge[i].Next){
        if(Edge[i].Ed!=Node[Now].Father&&Edge[i].Ed!=Node[Now].Son&&Edge[i].Exist){
            Node[Edge[i].Ed].Top=Edge[i].Ed;
            DFS2(Edge[i].Ed);
        }
    }
}
int LCA(int a,int b){
    while(Node[a].Top!=Node[b].Top){
        if(Node[Node[a].Top].Depth<Node[Node[b].Top].Depth){
            swap(a,b);
        }
        a=Node[Node[a].Top].Father;
    }
    return Node[a].Depth<Node[b].Depth?a:b;
}
void InitA(){
    for(int i=1;i<=n;i++) Father[i]=i;
    memset(Head,0,sizeof(Head));
    memset(DFN,0,sizeof(DFN));
}
void Init(int Now){
    Node[Now].Father=Now;
    Node[Now].Size=1;
    Node[Now].Top=Now;
    Node[Now].Depth=1;

}
struct Segment_Tree{
    int Count;
    struct NO{
        int LeftT,RightT,LeftN,RightN;
        int Data_Min;
    }Num[MAXN];
    void Build(int Left,int Right){
        Count++;
        Num[Count].LeftN=Left;
        Num[Count].RightN=Right;
        if(Left==Right){
            Num[Count].LeftT=Count;
            Num[Count].RightT=Count;
            Num[Count].Data_Min=Line[Left];
            return;
        }
        int Now=Count,Mid=(Left+Right)/2;
        Num[Count].LeftT=Count+1;
        Build(Left,Mid);
        Num[Now].RightT=Count+1;
        Build(Mid+1,Right);
        Num[Now].Data_Min=min(Num[Num[Now].LeftT].Data_Min,Num[Num[Now].RightT].Data_Min);
        return;
    }
    int Query_Min(int Now,int Left,int Right){
        if(Num[Now].LeftN>=Left&&Num[Now].RightN<=Right){return Num[Now].Data_Min;}
        if(Num[Now].LeftN>Right||Num[Now].RightN<Left){return INF;}
        else{
            return min(Query_Min(Num[Now].LeftT,Left,Right),Query_Min(Num[Now].RightT,Left,Right));
        }
    }
}Tree;
int Query_Path_Min(int Left,int Right){
    int Min=INF,Now;
    while(Node[Left].Top!=Node[Right].Top){
        if(Node[Node[Left].Top].Depth<Node[Node[Right].Top].Depth) Now=Right;
        else Now=Left;
        Min=min(Min,Tree.Query_Min(1,DFN[Node[Now].Top],DFN[Now]));
        if(Now==Left) Left=Node[Node[Now].Top].Father;
        else Right=Node[Node[Now].Top].Father;
    }
    return Node[Left].Depth<Node[Right].Depth?min(Min,Tree.Query_Min(1,DFN[Left],DFN[Right])):min(Min,Tree.Query_Min(1,DFN[Right],DFN[Left]));
}
int main(){
    memset(E,0,sizeof(E));
    int Q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&In1[i],&In2[i],&In3[i]);
        Edge_Add(In1[i],In2[i],In3[i]);
        Edge_Add(In2[i],In1[i],In3[i]);
    }
    InitA();
    Kruskal();
    Rebulid();
    for(int i=1;i<=n;i++){
        if(DFN[i]) continue;
        Init(i);
        DFS1(i);
        Give(i);
        DFS2(i);
    }
    int Q1,Q2;
    Tree.Count=0;
    Tree.Build(1,cnt);
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&Q1,&Q2);
        if(Find(Q1)!=Find(Q2)){
            printf("-1\n");
            continue;
        }
        int lca=LCA(Q1,Q2);
        int Ans=INF;
        for(int i=Head[lca];i;i=Edge[i].Next){
            int To=Edge[i].Ed;
            if(To==Node[lca].Father||!Edge[i].Exist) continue;
            if(LCA(To,Q1)==To){
                Ans=min(Ans,Query_Path_Min(To,Q1));
            }
            if(LCA(To,Q2)==To){
                Ans=min(Ans,Query_Path_Min(To,Q2));
            }
        }
        printf("%d\n",Ans);
    }
    return 0;
}