首页 > 其他 > 详细

(题目总结)LCA板子以及一些题目

时间:2019-04-15 20:43:15      阅读:265      评论:0      收藏:0      [点我收藏+]

 

---恢复内容开始---

LCA算法总结

把lca题目记入下来!分享给你们

板子tarjan(离线)

 

技术分享图片
#define N 10005
#define M 1000005
// N 表示的树的节点
// M 表示的问题数 
int cnt_e,cnt_q,head_e[N],head_q[N],vis[N],dis[N],t,ans[M],id[N],f[N];
// 边,问题数 
struct node{
    int u,w,next;
}e[N*2],q[M*2];
void init(){
    memset(head_e,-1,sizeof(head_e));
    memset(head_q,-1,sizeof(head_q));
    memset(vis,0,sizeof(vis));
    cnt_e=0;    
    cnt_q=0;
}
void addedge(int x,int y,int z){
    e[cnt_e].u=x;e[cnt_e].w=z;e[cnt_e].next=head_e[y];head_e[y]=cnt_e++;
    e[cnt_e].u=y;e[cnt_e].w=z;e[cnt_e].next=head_e[x];head_e[x]=cnt_e++;
}
void addquery(int x,int y,int z){
    q[cnt_q].u=x;q[cnt_q].w=z;q[cnt_q].next=head_q[y];head_q[y]=cnt_q++;
    q[cnt_q].u=y;q[cnt_q].w=z;q[cnt_q].next=head_q[x];head_q[x]=cnt_q++;
}
int find(int x){
    if(f[x] == x)
    return x;
    else
    return f[x] = find(f[x]);
}
void tarjan(int k){
    f[k]=k;
    vis[k]=1;
    id[k]=t;
    int i,v;
    for(i=head_q[k];i!=-1;i=q[i].next){
        v=q[i].u;
        if(vis[v]){
            
            // 表示的就是一颗树 
            // 每次只需要在这里做文章就行
            
            // ans[q[i].w] = find(v);                      //求的是lca 
            //ans[q[i].w]=dis[k]+dis[v]-2*dis[find(v)];    //求的是两个点的距离 
            
             
            //  solve1() 可以表示的是森林 
            //可以去求这个森林 
            
            if(id[v] == id[k])
            //ans[q[i].w] = find(v);
            ans[q[i].w] = dis[k]+dis[v]-2*dis[find(v)];
            else
            ans[q[i].w]=-1;
            
        }
    }
    for(i=head_e[k];i!=-1;i=e[i].next){
        v=e[i].u;
        if(!vis[v]){
            dis[v]=dis[k]+e[i].w;
            tarjan(v);
            f[v]=k;
        }
    }
}
View Code

 

 


LCA第一题:

给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先

 

 

题意:-------
我的理解:
直接套板子(因为是一颗树!直接套solve2)
AC 代码

技术分享图片
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<string>
#include<set>

typedef long long int ll;

using namespace std;

void read(int &x){
        int f=1;x=0;char s=getchar();
        while(s<0||s>9){if(s==-)f=-1;s=getchar();}
        while(s>=0&&s<=9){x=x*10+s-0;s=getchar();}
        x*=f;
}
#define N 500005
#define M 1000005
// N 表示的树的节点
// M 表示的问题数 
int cnt_e,cnt_q,head_e[N],head_q[N],vis[N],dis[N],t,ans[M],id[N],f[N];
// 边,问题数 
struct node{
    int u,w,next;
}e[N*2],q[M*2];
void init(){
    memset(head_e,-1,sizeof(head_e));
    memset(head_q,-1,sizeof(head_q));
    memset(vis,0,sizeof(vis));
    cnt_e=0;    
    cnt_q=0;
}
void addedge(int x,int y,int z){
    e[cnt_e].u=x;e[cnt_e].w=z;e[cnt_e].next=head_e[y];head_e[y]=cnt_e++;
    e[cnt_e].u=y;e[cnt_e].w=z;e[cnt_e].next=head_e[x];head_e[x]=cnt_e++;
}
void addquery(int x,int y,int z){
    q[cnt_q].u=x;q[cnt_q].w=z;q[cnt_q].next=head_q[y];head_q[y]=cnt_q++;
    q[cnt_q].u=y;q[cnt_q].w=z;q[cnt_q].next=head_q[x];head_q[x]=cnt_q++;
}
int find(int x){
    if(f[x] == x)
    return x;
    else
    return f[x] = find(f[x]);
}
void tarjan(int k){
    f[k]=k;
    vis[k]=1;
    id[k]=t;
    int i,v;
    for(i=head_q[k];i!=-1;i=q[i].next){
        v=q[i].u;
        if(vis[v]){
            
            // 表示的就是一颗树 
            // 每次只需要在这里做文章就行
            ans[q[i].w] = find(v);                      //求的是lca 
            //ans[q[i].w]=dis[k]+dis[v]-2*dis[find(v)];    //求的是两个点的距离 
            
             
            //  solve1() 可以表示的是森林 
            //可以去求这个森林 
            /*
            
            //ans[q[i].w] = find(v);
            ans[q[i].w] = dis[k]+dis[v]-2*dis[find(v)];
            else
            ans[q[i].w]=-1;
            */
        }
    }
    for(i=head_e[k];i!=-1;i=e[i].next){
        v=e[i].u;
        if(!vis[v]){
            dis[v]=dis[k]+e[i].w;
            tarjan(v);
            f[v]=k;
        }
    }
}

void solve1(){
    int n, m, cc, root, x, y, z;
    while(scanf("%d%d%d",&n,&cc,&m) == 3){
        init();
        while(cc--){
            //scanf("%d%d%d",&x,&y,&z);
            read(x),read(y),read(z);
            //z = 1;
            addedge(x,y,z);
        }
        for(int i = 0;i < m; i++){
            read(x),read(y);
            //scanf("%d%d",&x,&y);
            addquery(x,y,i);
        }
        t = 0;    // 这个是全局的变量
        for(int i = 1; i <= n; i++, t++){
            if(!vis[i]){
                dis[i] = 0;
                tarjan(i);
            }
        } 
        for(int i = 0; i < m; i++){
            if(ans[i] == -1){                    //                表示的就是不在一颗树 
                puts("Not connected");
            }else
                printf("%d\n",ans[i]);
        }
    } 
}
void solve2(){
    
    // 需要注意的就是这个tarjan 里面ans换下就可以求一颗树
    
    int tt ;
    
    //read(tt);
    tt = 1;
    while(tt--){
        int n, m, cc, root, x, y, z;
        read(n),read(m),read(root);
        init();
        for(int i = 1; i < n; i++){
            read(x),read(y);
            //read(z);
            z = 1;
            //scanf("%d%d%d",&x,&y,&z);
            addedge(x,y,z);
        } 
        for(int i = 0; i < m; i++){
            read(x),read(y);
            addquery(x,y,i);
        }
        // 一颗树的话,一般root 为1 ///只有一颗树,t 默认为0
        // root = 1;
        t = 0;  
        dis[root] = 0;
        tarjan(root);
        for(int i = 0; i < m; i++){
            printf("%d\n",ans[i]);
        } 
    }
}
int main(){
    
    int tt;
    //read(tt);
    tt = 1;
    while(tt--){
        // 1 表示的就是森林 
        //solve1();
        
        solve2();
    } 
    return 0;    
}
AC

 持续更新中

(题目总结)LCA板子以及一些题目

原文:https://www.cnblogs.com/daydaylee/p/10712886.html

(0)
(5)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!