Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

初涉Kruskal重构树

一种贼牛逼的思路,本来NOI之后就想学的,但一直到现在才学习…
考虑下面这个问题:给定一个无向连通图,求(x,y)路径上的最小值。
我会树连剖分!!
可以用Kruskal重构树解决,代码复杂度和常数大大下降。
(从小到大)将边权看成一个新点,将它与路径两点集合以父子关系连边。

这是核心过程:(新建节点从N+1开始标号)

void ReBuild_Kruskal(void){
    sort(E+1,E+M+1),Nd=N;
    for(int i=1;i<=N<<1;i++)Fa[i]=i;
    for(int i=1;i<=M;i++){
        int x=G(E[i].x),y=G(E[i].y);
        if(x^y){
            Fa[x]=Fa[y]=++Nd;
            Val[Nd]=E[i].c;
            Add(Nd,x),Add(Nd,y);
        }
    }
}

BZOJ3732Network

#include <cstdio>
#include <cctype>
#include <algorithm>
#define V 100005
using namespace std;

char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

int N,M,K,x,y,c,Fa[V],Val[V],F[17][V],Dep[V];
int head[V],nxt[V<<1],to[V<<1],Cnt,Nd;
#define Add(x,y) (nxt[++Cnt]=head[x],to[Cnt]=y,head[x]=Cnt)
struct Edge{int x,y,c;bool operator<(const Edge&x)const{return c<x.c;}}E[V];

int G(int x){
    return x==Fa[x]?x:Fa[x]=G(Fa[x]);
}
void ReBuild_Kruskal(void){
    sort(E+1,E+M+1),Nd=N;
    for(int i=1;i<=N<<1;i++)Fa[i]=i;
    for(int i=1;i<=M;i++){
        int x=G(E[i].x),y=G(E[i].y);
        if(x^y){
            Fa[x]=Fa[y]=++Nd;
            Val[Nd]=E[i].c;
            Add(Nd,x),Add(Nd,y);
        }
    }
}

void dfs(int x,int fa){Dep[x]=Dep[fa]+1,F[0][x]=fa;for(int i=head[x];i;i=nxt[i])if(to[i]^fa)dfs(to[i],x);}
void init(void){
    for(int i=1;(1<<i)<=Nd;i++)
        for(int j=1;j<=Nd;j++)F[i][j]=F[i-1][F[i-1][j]];
}

int LCA(int x,int y){
    if(Dep[x]<Dep[y])swap(x,y);
    for(int i=15;~i;i--)
        if(Dep[F[i][x]]>=Dep[y])x=F[i][x];
    if(x==y)return Val[x];
    for(int i=15;~i;i--)if(F[i][x]^F[i][y])x=F[i][x],y=F[i][y];
    return Val[F[0][x]];
}

int main()
{
    read(N),read(M),read(K);
    for(int i=1;i<=M;i++)read(E[i].x),read(E[i].y),read(E[i].c);
    ReBuild_Kruskal();
    dfs(Nd,0);
    for(init();K;K--){
        read(x),read(y);
        printf("%d\n",LCA(x,y));
    }
}

类似的题目还有NOIP2013货车运输

Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*