HDU 1330 Nearest Common Ancestors(求两个点的近期公共祖先)
2024-09-14 04:46:58
题目链接: id=1330">传送门
在线算法:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = 40010; struct nod{
int to,next,w;
}edge[maxn*2]; int head[maxn],ip,tot;
bool vis[maxn];
int R[maxn*2],ver[maxn*2];
int dp[maxn*2][25];
int first[maxn];
int dis[maxn];
bool isroot[maxn]; void init(){
memset(head,-1,sizeof(head));
memset(isroot,0,sizeof(isroot));
memset(vis,false,sizeof(vis));
dis[1]=0,ip=0,tot=0;
} void add(int u,int v){
edge[ip].to=v;
edge[ip].next=head[u];
head[u]=ip++;
}
/***
ver[i]=x:第i个点是x.
first[i]=x: 点i第一次出现的位置是x
R[i]=x:第i个点的深度为x;
dis[i]=x;点i到根节点的距离为x.
***/
void dfs(int u,int dept){
vis[u]=true,ver[++tot]=u,first[u]=tot,R[tot]=dept;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(!vis[v]){
dfs(v,dept+1);
ver[++tot]=u,R[tot]=dept;
}
}
} void ST(int n){
for(int i=1;i<=n;i++) dp[i][0]=i;
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)<=n;j++){
int a = dp[j][i-1],b=dp[j+(1<<(i-1))][i-1];
if(R[a]<R[b]) dp[j][i]=a;
else dp[j][i]=b;
}
}
} int RMQ(int l,int r){
int k=0;
while(1<<(k+1)<=r-l+1)
k++;
int x = dp[l][k], y=dp[r-(1<<k)+1][k];
if(R[x]<R[y]) return x;
else return y;
} int LCA(int u,int v){
u=first[u],v=first[v];
if(u>v) swap(u,v);
return ver[RMQ(u,v)];
} int main(){
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
init();
for(int i=0;i<n-1;i++){
int u,v,w;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
isroot[v]=1;
}
int x,y;
scanf("%d%d",&x,&y);
int root;
for(int i=1;i<=n;i++){
if(!isroot[i]){
root=i;
break;
}
}
dfs(root,1);
ST(n*2-1);
printf("%d\n",LCA(x,y));
}
return 0;
}
离线算法:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = 40010; struct nod{
int u,v,next,w,lca;
}edge[maxn*2],edge1[maxn]; int par[maxn],ancestors[maxn];
int head[maxn];
int dis[maxn],ip;
int x,y;
bool vis[maxn];
bool root[maxn]; void init(){
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
for(int i=0;i<maxn;i++) root[i]=true;
for(int i=1;i<maxn;i++) par[i]=i;
ip=0;
} int find_par(int x){
if(x!=par[x]) return par[x]=find_par(par[x]);
return par[x];
} void Union(int u,int v){
u=find_par(u);
v=find_par(v);
if(u!=v) par[v]=u;
} void add(int u,int v){
edge[ip].v=v;
edge[ip].next=head[u];
head[u]=ip++;
} bool ans; void tarjan(int u){
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(!vis[v]){
dis[v]=dis[u]+edge[i].w;
tarjan(v);
Union(u,v);
}
}
if(u==x&&vis[y]&&!ans){
ans=1;
printf("%d\n",find_par(y));
return;
}
if(u==y&&vis[x]&&!ans){
ans=1;
printf("%d\n",find_par(x));
return;
}
} int main()
{
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
init();
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
root[v]=false;
add(u,v);
add(v,u);
}
ans=0;
scanf("%d%d",&x,&y);
for(int i=1;i<=n;i++){
if(root[i]){
tarjan(i);
break;
}
}
}
return 0;
}
最新文章
- ffmpeg+x264 Windows MSVC 静态编译
- DBCP配置数据库连接乱码问题
- Redis Cluster 3.0搭建与使用
- 异常:exception和error的区别
- java 中的异常处理
- C#网络编程简单实现通信小例子-2
- java Permissions and Security Policy--官方文档
- Oracle EBS-SQL (INV-10):检查库存接口.sql
- list-列表功能介绍
- echarts 修改y轴name的样式
- linux学习笔记整理(二)
- Symfony2 学习笔记之控制器
- vue组件生命周期详解
- MATLAB 图像归一化
- HDU1042N!大数的阶乘java模板
- opencv画图
- ios audio不能自动播放
- 优雅退出telnet
- go chapter 6 - map array
- Adaptive Query Optimization in Oracle Database 12c (12.1 and 12.2)
热门文章
- c语言变量名称与变量
- 「拒絕存取路徑 &#39;C:\Users\xxx\AppData\Local\Temp\Temporary ASP.NET Files\apname\3a1b3704\f7fc6d0c\App_Code.l8ieogii.0.cs」的錯誤!
- BZOJ2668: [cqoi2012]交换棋子
- [swustoj 1092] 二分查找的最大次数
- android studio 安装总结
- 【 D3.js 高级系列 — 2.0 】 捆图
- 【Java】Java运行cmd命令直接导出.sql文件
- Using SharePoint 2010 dialogs
- Breaking parallel loops in .NET C# using the Stop method z
- UVA 10600 ACM Contest and Blackout 次小生成树