POJ1986,Distance Queries(LCA)
程序员文章站
2022-05-27 16:15:23
...
这道题可以用LCA做出来,虽然最短路可以做出来,但是询问次数很多,每询问一次就求一次最短路的话,时间开销是很大的。
这里我是用LCA转化为RMQ求出来,需要注意的一点就是题所给的图可能不是连通的,所以在DFS的时候要稍作改变。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
int depth[2*maxn],id[2*maxn],in[maxn],num;
int dp[2*maxn][15],dis[maxn]; //dis[i]是记录根到i节点的最短距离
bool vis[maxn]; //vis[i]标记i节点是否访问过
struct Edge
{
int v,cost;
Edge(int v,int cost) { this->v=v; this->cost=cost; };
};
vector<Edge> G[maxn];
void addedge(int u,int v,int w)
{
G[u].push_back( Edge(v,w) );
G[v].push_back( Edge(u,w) );
}
void DFS(int u,int pre,int d)
{
id[++num]=u;
in[u]=num;
depth[num]=d;
vis[u]=1;
for(int i=0;i<G[u].size();++i)
{
Edge e=G[u][i];
if(!vis[e.v])
{
dis[e.v]=dis[u]+e.cost;
DFS(e.v,u,d+1);
id[++num]=u;
depth[num]=d;
}
}
}
void init(int n)
{
for(int i=1;i<=n;++i) dp[i][0]=i;
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i+(1<<j)-1<=n;++i)
{
int a=dp[i][j-1], b=dp[i+(1<<(j-1))][j-1];
if(depth[a]<depth[b]) dp[i][j]=a;
else dp[i][j]=b;
}
}
int RMQ(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1) ++k;
int a=dp[l][k], b=dp[r-(1<<k)+1][k];
return depth[a]<depth[b]? a:b;
}
int LCA(int u,int v)
{
int l,r;
l=in[u]; r=in[v];
if(l>r) swap(l,r);
return id[RMQ(l,r)];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int u,v,w; char s[10];
scanf("%d%d%d%s",&u,&v,&w,s);
addedge(u,v,w);
}
num=0;
for(int i=1;i<=n;++i) vis[i]=0;
for(int i=1;i<=n;++i)
{
if(!vis[i])
{
dis[i]=0; //根到根的距离为0
DFS(i,-1,1);
}
}
init(2*n-1);
int k;
scanf("%d",&k);
while(k--)
{
int u,v;
scanf("%d%d",&u,&v);
int lca=LCA(u,v);
printf("%d\n",dis[u]+dis[v]-2*dis[lca]);
}
return 0;
}
推荐阅读
-
Codeforces Round #620 (Div. 2) E. 1-Trees and Queries(LCA+思维)
-
POJ1986(Distance Queries)
-
POJ 1986 Distance Queries (Tarjan算法求最近公共祖先)
-
POJ1986,Distance Queries(LCA)
-
poj1986 Distance Queries(lca又是一道模版题)
-
Distance Queries POJ - 1986(最近公共祖先)
-
POJ1986:Distance Queries(LCA求距离 + Tarjan)
-
POJ 1986 Distance Queries(求最近公共祖先,LCA-Tarjan)
-
poj1986 Distance Queries (lca模板)
-
Distance Queries POJ - 1986 (tarjan离线LCA)