admin 管理员组文章数量: 887021
例题
贴几篇LCA知识点的博客详解：
CSDN - 青烟绕指柔!的博客 - 倍增算法
CSDN - Nekroz_的博客
CSDN - Dust_Heart的博客
CSDN - creatorx的博客 -Tarjan算法
洛谷P3379 【模板】最近公共祖先（LCA）
倍增模板题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <stdio.h>
using namespace std;// LCA 最近公共祖先 倍增const int N = 5e5+10;
int n ,m ,s;
int e[2*N], pr[2*N], h[2*N], idx = 0; // 链式前向星
int depth[N], f[N][30]; // depth[]深度 f[i][j]是i的2^j级祖先// 加边 （两个无向边）
void add(int x, int y){e[++idx] = y, pr[idx] = h[x], h[x] = idx;
}// dfs得到每一点的 深度 和 所有祖先 ，根结点深度为1
void dfs(int x, int fa){depth[x] = depth[fa]+1, f[x][0] = fa;for(int i = 1; (1<<i) <= depth[x]; i++) f[x][i] = f[f[x][i-1]][i-1];for(int i = h[x]; i; i = pr[i]) {if(e[i] != fa) dfs(e[i],x);}
}// 计算最近公共祖先 倍增
int lca(int x, int y){//1. 将x y跳到同一层（同一高度）//2. 将x y按照距离从高到低跳，若祖先相同，说明此时有跳过的可能，继续看下一次；// 若不同则跳到该层，从该层继续跳（不会跳不到，可以手动模拟一下）if(depth[x] < depth[y]) swap(x,y);while(depth[x] > depth[y]) x = f[x][(int)(log2(depth[x] - depth[y]))];if(x == y) return x;for(int i = log2(depth[x]); i >= 0; i--)if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];return f[x][0];
}int main(){// n-1条无向边 m次询问 s为根节点scanf("%d%d%d",&n,&m,&s);for(int i = 1; i < n; i++){int x, y;scanf("%d%d",&x,&y);add(x,y), add(y,x);}dfs(s,0);while(m--){int a,b;scanf("%d%d",&a,&b);cout<<lca(a,b)<<endl;}return 0;
}
POJ1330 - Nearest Common Ancestors
- 链接：Nearest Common Ancestors
水题…两遍bfs也能过…贴一个lca的代码…顺便吐槽一下poj每次提交都得CE几发
倍增代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <queue>
using namespace std;const int N = 1e5+10;
int e[N], pr[N], h[N], idx = 0;
int f[N][30], depth[N], in[N];double l2(double x){return log(x)/log(2.0);
}void add(int x, int y){e[++idx] = y, pr[idx] = h[x], h[x] = idx;
}void bfs(int x, int fa){depth[x] = depth[fa]+1, f[x][0] = fa;for(int i = 1; i <= l2(depth[x]); i++) f[x][i] = f[f[x][i-1]][i-1];for(int i = h[x]; i; i = pr[i]){if(e[i] != fa) bfs(e[i], x);}
}int lca(int x, int y){if(depth[x] < depth[y]) swap(x,y);while(depth[x] > depth[y]) x = f[x][(int)l2(depth[x] - depth[y])];if(x == y) return x;for(int i = l2(depth[x]); i >= 0; i--){if(f[x][i] != f[y][i]) x = f[x][i], y= f[y][i];}return f[x][0];
}int main(){int cas; scanf("%d",&cas);while(cas--){idx = 0;memset(h, 0, sizeof h);memset(in, 0 ,sizeof in);int n; scanf("%d",&n);for(int i = 1; i < n ;i ++){int x , y; scanf("%d%d",&x, &y);add(x,y); in[y]++;}for(int i = 1; i <= n; i++)if(!in[i]) depth[0] = 0, bfs(i,0);int x, y;cin>>x>>y;cout<< lca(x,y) <<endl;}return 0;
}POJ1470 - Closest Common Ancestors
- 链接：=1470
- 离线Tarjan
#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <set>
#include <vector>
using namespace std;const int N = 1e3+10;
int in[N], fa[N], vis[N], ask[N][N], n, num[N];
vector<int>g[N];void init(){memset(in,0,sizeof in);memset(ask,0,sizeof ask);memset(vis, 0, sizeof vis);memset(num, 0 ,sizeof num);for(int i = 1; i <= n; i++){g[i].clear();fa[i] = i;}
}int fin(int x){if(fa[x] == x) return x;return fa[x] = fin(fa[x]);
}void lca(int r){for(int i = 1; i <= n; i++)if(vis[i] && ask[r][i]) num[fin(i)] += ask[r][i];vis[r] = 1;for(int i = 0; i < g[r].size(); i++){int t = g[r][i];lca(t);fa[t] = r;}
}int main(){while(~scanf("%d",&n)){init();int x, m, y;for(int i = 1; i <= n; i++) {scanf("%d:(%d)",&x,&m);while(m--){scanf("%d",&y);g[x].push_back(y);in[y] ++;}}scanf("%d",&m);while(m--){scanf(" (%d %d)",&x,&y);ask[x][y] ++, ask[y][x] ++;}for(int i = 1; i <= n; i++){if(!in[i]) lca(i);}for(int i = 1; i <= n; i++) if(num[i]) cout<<i<<':'<<num[i]<<endl;}return 0;}
本文标签： 例题
版权声明：本文标题：例题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688099221h179145.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论