精华内容
下载资源
问答
  • lca倍增

    2016-09-11 12:02:26
    经过学习和(抄袭)学会了lca倍增。 跳表?acs[x][i]:x上2 i步的祖先 每次查找最大能减去2 i 提到同一高度 然后再一起上升找到祖先 #include #include #include using namespace std; int n,m,u,v; int used...

    经过学习和(抄袭)学会了lca倍增。

    跳表?acs[x][i]:x上2 i步的祖先

    每次查找最大能减去2 i 提到同一高度

    然后再一起上升找到祖先

    #include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;
    int n,m,u,v;
    int used[100010],dis[100010],dep[100010];
    int acs[100010][23];
    vector<int>graph[100010];
    void dfs(int u,int d)
    {
    	used[u]=1;
    	dep[u]=d;
    	for(int i=0;i<graph[u].size();i++)
    	{
    		int v=graph[u][i];
    		if(!used[v])
    		{
    			acs[v][0]=u;
    			dfs(v,d+1);
    		}
    	}
    }	
    void get_acs()
    {
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=22;j++)
    		{
    			if(acs[i][j-1]<0)
    				acs[i][j]=-1;
    			else
    				acs[i][j]=acs[acs[i][j-1]][j-1];
    		}
    }
    int lca(int x,int y)
    {	
    	if(dep[x]<dep[y])
    		swap(x,y);
    	for(int k=22;k>=0;k--)
    	{
    		if(acs[x][k]!=-1&&dep[acs[x][k]]>=dep[y])
    			x=acs[x][k];
    	}
    	if(x==y)
    		return x;
    	for(int k=22;k>=0;k--)
    	{
    		if(acs[x][k]!=acs[y][k])
    		{
    			x=acs[x][k];
    			y=acs[y][k];
    		}
    	}
    	return acs[x][0];
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>u>>v;
    		graph[u].push_back(v);
    		graph[v].push_back(u);
    	} 
    	memset(acs,-1,sizeof(acs));
    	dfs(1,1);
    	get_acs();
    	while(cin>>u>>v)
    	{
    		cout<<lca(u,v)<<endl;
    	}
    	return 0;
    }


    展开全文
  • LCA倍增

    2019-07-04 19:57:00
    想探讨一下lca问题的倍增解法 以洛谷第3379题为例 代码如下: #include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; //建树邻接表; ...

    想探讨一下lca问题的倍增解法

    以洛谷第3379题为例

    代码如下:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cctype>
    using namespace std;
    //建树邻接表;
    int n,m,s,x,y,a,b,ans[500005];
    int fir[500005],nex[500005],to[500005],tot,top;
    int dep[500004],f[500005][22];
    void build(int x,int y){
        to[++tot]=y; 
        nex[tot]=fir[x];
        fir[x]=tot;
    } 
    inline int read(){
      int X=0,w=0; char ch=0;
      while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
      while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
      return w?-X:X;
    }
    //预处理;
    void deal_f(int u,int father){
        dep[u]=dep[father]+1;
        for(int i=0;i<=19;i++)
          f[u][i+1]=f[f[u][i]][i];//推出来的;
        for(int e=fir[u];e;e=nex[e]){
          int v=to[e];
          if(v==father) continue;//不处理,无意义;        
          f[v][0]=u;
          deal_f(v,u);//找寻相关子父点;
    }
    }
    //LCA,自己仔细想一下;
    int lac(int a,int b){
        if(dep[a]<dep[b]) swap(a,b);
        for(int i=20;i>=0;i--){
          if(dep[f[a][i]]>=dep[b]) a=f[a][i];//从上下调; 
          if(a==b) return a;
    }  
        for(int i=20;i>=0;i--){
         if(f[a][i]!=f[b][i]){
         a=f[a][i];
         b=f[b][i];
    }
    }
        return f[a][0];
    }
    
    int main(){
       scanf("%d%d%d",&n,&m,&s);
       for(int i=1;i<=n-1;i++){
         x=read();y=read();//scanf("%d%d",&x,&y);
         build(x,y);build(y,x);//无向图;
    }
       deal_f(s,0);//因题中已确定根节点;
       for(int i=1;i<=m;i++){
         a=read();b=read();//scanf("%d%d",&a,&b);
         ans[i]=lac(a,b);
    }
       for(int i=1;i<=m;i++){
         printf("%d\n",ans[i]);
    }
    }

     


    假如用这个代码有三个点过不去。

    究其原因是时间超限。

    那么解决方法是(参考了大佬的解决方法,但在此具体提出,为我们这些有点晕的人

    那就是你没注意数组的大小,我边打边写现在想哭3个小时就是因为数组开小了

    将题中nex数组×2和to数组×2,即可;

    第一次写有点水,见谅;

     

    转载于:https://www.cnblogs.com/WH-GR/p/11134591.html

    展开全文
  • LCA 倍增

    2019-08-05 12:45:47
    假设我们要求x 和y 的LCA。 将x 和y 中深度较大的那个往上跳到和另一个深度相同。 再同时向上倍增枚举一个2 的幂的步长2i,若x 往上走2i 步与y 往上走2i 步不为同一个点,则将它们同时往上走2i 步。...

    预处理出f[i][j] 表示j 点往上走2i 步到达的点。
    f[0][j]=father[j]
    f[i][j]=f[i-1][f[i-1][j]]
    预处理时间复杂度O(n log n)
    假设我们要求x 和y 的LCA。
    将x 和y 中深度较大的那个往上跳到和另一个深度相同。
    再同时向上倍增枚举一个2 的幂的步长2i,若x 往上走2i
    步与y 往上走2i 步不为同一个点,则将它们同时往上走2i
    步。
    这时只有两种情况:x = y 或
    lca(x; y) = father[x] = father[y]。
    查询时间复杂度O(log n)

    展开全文
  • LCA倍增 模板

    2018-08-08 13:56:00
    LCA倍增 最近公共祖先 构造 NlogN 查询 ogN 先调用pre()构造对数数组 再调用dfs(root, 0, 0)查询深度 再调用work()构造跳表 最后调用lca(u, v)查询在有根树中节点u和v的最近公共祖先 const int N = 10005; ...

    LCA倍增 最近公共祖先

    构造 NlogN 查询 ogN

    先调用pre()构造对数数组 再调用dfs(root, 0, 0)查询深度 再调用work()构造跳表

    最后调用lca(u, v)查询在有根树中节点u和v的最近公共祖先

    const int N = 10005;
    struct edge  { int to, next; } e[N << 1];
    int n, head[N];
    namespace LCA
    {
        int log[N], depth[N], deg[N], par[N][30];
        inline void pre()
        {
            log[1] = 0;
            for (int i = 2; i < N; ++i)
            {
                log[i] = log[i - 1];
                if ((1 << (log[i] + 1)) == i)   log[i]++;
            }
        }
        void dfs(int u, int fa, int dep)
        {
            depth[u] = dep;
            par[u][0] = fa;
            for (int i = head[u]; i; i = e[i].next)
            {
                int v = e[i].to;
                if (v == fa)    continue;
                dfs(v, u, dep + 1);
            }
        }
        inline void work()
        {
            for (int j = 1; j <= log[n]; ++j)
                for (int i = 1; i <= n; ++i)
                    par[i][j] = par[par[i][j - 1]][j - 1];
        }
        inline int lca(int u, int v)
        {
            if (depth[u] < depth[v])    std::swap(u, v);
    
            int t = depth[u] - depth[v];
            for (int j = 0; j <= log[n]; ++j)
                if (t >> j & 1) u = par[u][j];
    
            if (u == v) return u;
    
            for (int i = log[n]; ~i; --i)
                if (par[u][i] != par[v][i])
                {
                    u = par[u][i];
                    v = par[v][i];
                }
    
            return par[u][0];
        }
    }
    
    展开全文
  • LCA倍增标程

    2017-02-13 11:43:35
    LCA倍增标程#include #include #include using namespace std; int n,m,s,x,y; struct {int to,next;}a[1000010]; int head[500010],deep[500010],zx[500010][20],tot; void build(int x,int y)
  • 博客:最近公共祖先 LCA 倍增法 博客:浅谈倍增法求LCA 二、沙场练兵 题目:POJ 1330Nearest Common Ancestors 代码: const int MAXN = 10010; const int DEG = 20; struct Edge { int to,...
  • LCA倍增解法

    千次阅读 2020-08-19 23:05:42
    先讲讲暴力思路吧,懂了暴力这个再用倍增优化会比较好理解。 暴力思路,首先维护两个数组: 1.depth[vertice]表示vertice的深度 2.father[vertice]表示vertice的上一个祖先 既然是最近公共祖先,那么我们先把两个点u...
  • 上一套基于二分搜索的lca倍增算法模板 #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; #define exp 1e-8...
  • 最近公共祖先 LCA 倍增算法倍增算法可以在线求树上两个点的LCA,时间复杂度为nlogn预处理:通过dfs遍历,记录每个节点到根节点的距离dist[u],深度d[u]init()求出树上每个节点u的2^i祖先p[u][i]求最近公共祖先,根据...
  • lca倍增模板

    2020-03-14 03:56:20
    lca即最近公共祖先,倍增法可以在O(n)的预处理后以每次logn的代价进行查询操作。 思路:预处理出fa[n][i]数组,表示第n号点的第(1<<i)个父亲,之后在寻找u、v的lca时,可以对二进制上的每一位进行向上跳跃。...
  • ACM LCA 倍增 模板 HDU 5044

    千次阅读 2014-09-27 18:20:41
    LCA 倍增模板O(N*log N),N为点数 最近公共祖先
  • LCA倍增 倍增利用了二进制的特性;LCA为求公共祖先。 利用倍增的典型算法还有RMQ。 题目代码 #include&lt;cstdio&gt; #include&lt;vector&gt; #include&lt;string&gt; #include&...
  • 次小生成树(LCA倍增)

    2019-09-27 14:51:45
    利用LCA倍增地维护最小生成树上两点之间的最大边权 每次枚举在MST之外的边 有两种情况 ①.两个端点在一条链上 ②.两个端点不在一条链上 第一种情况就直接得到答案 第二种情况的话分两步处理取MAX 严格 bzoj1977 ...
  • LCA倍增算法

    2018-03-16 12:40:00
    这里我实现LCA是通过倍增,其实就是二进制优化。 任何一个数都可以有2的阶数实现 例如16可以由1 2 4 8组合得到 5可以由1 2 4 组合得到 便于读者理解 我放一道例题吧 Problem F: 挑战迷宫 Description 小翔和...
  • LCA 倍增模版

    2018-08-11 16:15:12
    倍增算法可以在线求树上两个点的LCA,时间复杂度为nlogn 预处理:通过dfs遍历,记录每个节点到根节点的距离dis[u],深度dep[u] i的2^j祖先就是i的(2^(j-1))祖先的2^(j-1)祖先: ///倍增算法 const int maxn = 1e...
  • LCA 倍增+O(1)

    2018-06-10 18:31:15
    LCA 倍增算法 时间复杂度为O(NlogN)O(NlogN)O(NlogN)的在线算法 Dep[v]Dep[v]Dep[v]记录节点vvv的深度,Fa[v][k]Fa[v][k]Fa[v][k]记录vvv向上第2k2k2^k个祖先的编号 代码 #include&amp;amp;amp;amp;amp;...
  • LCA 倍增模板

    2020-09-21 16:59:47
    } } int lca(int u, int v) { if(depth[u] [v]) swap(u,v); for(int i=20; i>=0; --i) { if(depth[f[u][i]]>=depth[v]) { u=f[u][i]; } if(u==v) return u; } for(int i=20; i>=0; --i) { if(f[u][i]!=f[v][i]) { u...
  • LCA 倍增算法

    2019-05-11 09:53:12
    struct LCA { struct edge { int from, to, w, nxt; }edges[MAXN << 3]; int head[MAXN], cnt, n; int id[MAXN], dep[MAXN], dist[MAXN]; int fa[MAXN][32]; void ad...
  • LCA倍增模板

    2019-02-25 09:07:14
    求a, b的lca code #include &amp;lt;algorithm&amp;gt; #include &amp;lt;cctype&amp;gt; #include &amp;lt;cmath&amp;gt; #include &amp;lt;complex&amp;gt; #include &amp;lt...
  • lca 倍增模版

    2019-10-07 17:21:50
    lca( int a, int b ){ if ( d[a] > d[b] ) a ^= b, b ^= a, a ^= b; if ( d[a] < d[b] ){ int del = d[b] - d[a]; for ( int i = 0 ; i ; i++ ) if (del&( 1 )) b= p[b][i]; } if ( a != b ){ ...
  • lca 倍增

    2019-09-25 09:00:32
    题目链接: ... AC代码: 1 #include 2 #include ... lca( ...,lca(t1,t2)); 85 } 86 return 0 ; 87 } 88   转载于:https://www.cnblogs.com/letlifestop/p/10262798.html

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,113
精华内容 1,245
关键字:

lca倍增