最小公共祖先 模板+洛谷p1967
程序员文章站
2022-04-11 10:24:04
...
一、(LCA)
倍增思想,优化了暴力找公共祖先
#include <stdio.h>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;
int head[500005],nex[500005*2],ver[500005*2];
int tot,t,s,d[500005],fa[500005][20]; //fa[i][j]表示i结点2^j的祖先结点,倍增思想
void add(int u,int v)
{
nex[++tot]=head[u];
ver[tot]=v;
head[u]=tot;
}
void bfs() //确定分层,也就是每个结点的深度,在不确定根结点时也可以做
{ //因为建的是双向图,不影响结果
queue<int>q;
d[s]=1; //根结点为深度1
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=nex[i])
{
int v=ver[i];
if(d[v])continue;
d[v]=d[u]+1; //字结点是父亲结点深度+1
fa[v][0]=u; //v往上爬2^0格是u
for(int j=1;j<=t;j++) //求出v结点的倍增结点,t是我们算出的最大深度2^t
fa[v][j]=fa[fa[v][j-1]][j-1]; //可以理解成这个结点的爷爷是它爸爸的爸爸
q.push(v);
}
}
}
int lca(int x,int y)
{
if(d[x]>d[y])swap(x,y); //让x比y高
for(int i=t;i>=0;i--) //让y与x在同一层
if(d[fa[y][i]]>=d[x])y=fa[y][i];
if(x==y)return x; //两个相等 则x是公共祖先
for(int i=t;i>=0;i--) //如果两个的祖先不属于不相等,两个都可以往上跳
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; //根据二进制思想最后他们就差一步到达公共祖先
return fa[x][0];
}
int main()
{
int n,m,u,v;
scanf("%d%d%d",&n,&m,&s);
t=(int)(log(n)/log(2))+1;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
bfs();
while(m--)
{
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
}
二、tarjan 离线算法
参考 https://www.cnblogs.com/JVxie/p/4854719.html
Tarjan(u)//marge和find为并查集合并函数和查找函数
{
for each(u,v) //访问所有u子节点v
{
Tarjan(v); //继续往下遍历
marge(u,v); //合并v到u上
标记v被访问过;
}
for each(u,e) //访问所有和u有询问关系的e
{
如果e被访问过;
u,e的最近公共祖先为find(e);
}
}
当前将要回溯的点,和它相连的点如果被访问过,那它们的公共祖先就是那个点并查集所并入的点。
比如
x 是y的祖先,那由于x还没被回溯,fa【x】=x,那答案是x
x不是y的祖先,那在某个分支x被并入了t点,而y是t的子孙。
#include <stdio.h>
#include <vector>
using namespace std;
int head[500005],nex[500005*2],ver[500005*2];
int tot,fa[500005],ans[500005];
bool vis[500005];
vector<int>query[500005],query_id[500005]; //用来存询问的u,v和id
void add(int u,int v)
{
nex[++tot]=head[u];
ver[tot]=v;
head[u]=tot;
}
void add_query(int u,int v,int id) //也可以用链式前向星
{
query[u].push_back(v),query_id[u].push_back(id); //要存两边,因为回溯x是可能并没有
query[v].push_back(u),query_id[v].push_back(id); //访问过y,这样无法确定公共祖先
}
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void tarjan(int u)
{
vis[u]=1; 标记v被访问过;
for(int i=head[u];i;i=nex[i])
{
int v=ver[i];
if(!vis[v])
{
tarjan(v); //继续往下遍历
fa[v]=find(u); //合并v到u上
}
}
for(int i=0;i<query[u].size();i++)
{
int v=query[u][i],id=query_id[u][i];
if(vis[v])
ans[id]=find(v); // 如果e被访问过;
//u,e的最近公共祖先为find(e);
}
}
int main()
{
int n,m,s,u,v;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
fa[i]=i;
}
fa[n]=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add_query(u,v,i);
}
tarjan(s);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
https://www.luogu.org/problem/P1967
题目描述
A 国有 nn 座城市,编号从 11 到 nn,城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制,简称限重。
现在有 qq 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道路。
接下来 mm 行每行三个整数 x, y, z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。 注意: x !=y,两座城市之间可能有多条道路 。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x,y,之间用一个空格隔开,表示一辆货车需要从 xx 城市运输货物到 yy 城市,保证 x !=y
输出格式
共有 q行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。 如果货车不能到达目的地,输出−1。
输入
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出
3
-1
3
大佬思路
因为可能会有多个森林所以要用并查集来确认两个点是否为相连
#include <stdio.h>
#include <queue>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
int head[10005],nex[20005],ver[20005],d[20005];
int f[10005],fa[10005][16],w[10005][16],dep[10005],tot,t,n,m;
struct node //用来存原图
{
int u,v,d;
bool operator<(const node &a)const {return d>a.d;};
}edge[50005];
void add(int u,int v,int z) //存新图
{
nex[++tot]=head[u];
ver[tot]=v;
d[tot]=z;
head[u]=tot;
}
int find(int x) //因为可能会有多个森林所以要用并查集来确认两个点是否为相连
{
return x==f[x]?x:f[x]=find(f[x]);
}
void kruskal() //构成最大生成树
{
for(int i=1;i<=n;i++)f[i]=i;
sort(edge+1,edge+1+m);
for(int i=1;i<=m;i++)
{
int x=find(edge[i].u),y=find(edge[i].v);
if(x==y)continue;
f[x]=y;
add(edge[i].u,edge[i].v,edge[i].d),add(edge[i].v,edge[i].u,edge[i].d);
}
}
void bfs(int s) //用来给每个森林的结点分深度
{
queue<int>q;
dep[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=nex[i])
{
int v=ver[i];
if(dep[v])continue;
dep[v]=dep[u]+1;
fa[v][0]=u;
w[v][0]=d[i];
for(int j=1;j<=t;j++)
{
fa[v][j]=fa[fa[v][j-1]][j-1];
w[v][j]=min(w[v][j-1],w[fa[v][j-1]][j-1]); //因为是从上往下计算的,所以w【i】【j】存的是它到2^j的最小值。倍增思想
}
q.push(v);
}
}
}
/*int dfs(int x,int pre,int val) //同bfs
{
dep[x]=dep[pre]+1;
w[x][0]=val;
fa[x][0]=pre;
for(int i=1;i<=t;i++)
{
fa[x][i]=fa[fa[x][i-1]][i-1];
w[x][i]=min(w[x][i-1],w[fa[x][i-1]][i-1]);
}
for(int i=head[x];i;i=nex[i])
if(!dep[ver[i]])
dfs(ver[i],x,d[i]);
}*/
int lca(int x,int y)
{
if(find(x)!=find(y))return -1; //不属于同一个森林
int ans=1e9; //每次跳转都要更新ans
if(dep[x]>dep[y])swap(x,y);
for(int i=t;i>=0;i--)
if(dep[fa[y][i]]>=dep[x])ans=min(ans,w[y][i]),y=fa[y][i];
if(x==y)return ans;
for(int i=t;i>=0;i--)
if(fa[x][i]!=fa[y][i])
{
ans=min(ans,min(w[x][i],w[y][i]));
x=fa[x][i];y=fa[y][i];
}
ans=min(ans,min(w[x][0],w[y][0]));
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
t=(int)(log(n)/log(2))+1;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].d);
kruskal();
for(int i=1;i<=n;i++)
if(!dep[i])bfs(i);
//for(int i=1;i<=n;i++)
//if(i==f[i])dfs(i,i,1e9);
int q,u,v;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
}