刚刚学了Kruskal重构树,然后打了一个模板,现在趁热打一个博客。。。

我们来看一道裸体:

火狐截图_2018-07-24T12-11-20.140Z

这道题看起来好像很水,我们可以跑最小生成树然后套一个倍增LCA,统计路径上的最大值。。。但我们现在用一个更加奇妙的方法来做。。。叫做Kruskal重构树。。。

我们思考一下我们做Kruskal的过程,就是从小到大加边,那么我们可知加入的边是递增的,那么一条连上的最大边值,一定是后加入的,那我们只要创造一种结构,后加入的边在结构的上面,每次直接LCA就求出答案。。。没错就是它。。。

我们思考加入边时,我们建立一个虚拟节点,把两个节点连到虚拟节点上。。。

然后当我们合并两棵树时,我们直接把虚拟节点连到新建的虚拟节点上就好了。。。最后我们发现所有原树上的节点都是树的底层叶子,他们没有儿子。。。

这棵建好的树有很多好的性质,所有虚拟节点的权值都小于其父亲,而且这是一颗二叉树。。。

那么我们询问两个点之间的最大边值时,直接跳LCA,输出其节点的值就ok了。。。

 直接上代码吧:

#include<bits/stdc+.h>
#define LL long long
using namespace std;
const LL N=15e3+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO 
{
    template inline void read(tp &x) 
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x) 
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x) 
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,m,fa[N*2],cnt,k;
int fath[N*2][22],dep[N*2];
int val[N*2],ch[N*2][2];
struct Undirected_graph{int from,to,cost;}figure[N*2];
bool cmp(Undirected_graph a,Undirected_graph b){return a.cost<b.cost;}
int get_fa(int now)
{
    if(fa[now]==now)return now;
    return fa[now]=get_fa(fa[now]);
}
//----------------核心代码------------------
void build()
{
    int flag=0;
    for(int i=1;i<=m;i++)
    {
        int from=figure[i].from,to=figure[i].to,cost=figure[i].cost;
        if(flag==n-1)break;
        if(get_fa(from)==get_fa(to))continue;
        val[++cnt]=cost;
        ch[cnt][0]=fa[from],ch[cnt][1]=fa[to];
        fath[fa[from]][0]=fath[fa[to]][0]=cnt;
        fa[fa[from]]=fa[fa[to]]=cnt;flag++;
    }
}
//---------------核心代码---------------------
void dfs(int now)
{
    if(now==0)return;
    for(int i=1;i<=20;i++)
        fath[now][i]=fath[fath[now][i-1]][i-1];
    dep[ch[now][0]]=dep[ch[now][1]]=1+dep[now]+1;
    dfs(ch[now][0]),dfs(ch[now][1]);
}
int lca(int l,int r)
{
    if(dep[l]=0;i--)
        if(dep[fath[l][i]]>=dep[r])
            l=fath[l][i];
    if(l==r) return val[l];
    for(int i=20;i>=0;i--)
        if(fath[l][i]!=fath[r][i])
            l=fath[l][i],r=fath[r][i];
    return val[fath[l][0]];
}
main() 
{
    read(n),read(m),read(k);cnt=n;
    for(int i=1;i<=m;i++)
        read(figure[i].from),read(figure[i].to),read(figure[i].cost);
    sort(figure+1,figure+m+1,cmp);
    for(int i=1;i<=n*2;i++) fa[i]=i,fath[i][0]=i;
    build();dep[cnt]=1;
    dfs(cnt);
    for(int i=1;i<=k;i++)
    {
        int l,r;
        read(l),read(r);
        writeln(lca(l,r));
    }
    return 0;
}

Leave A Comment

发表评论

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