正文

POJ 1986 Distance Queries （Tarjan算法求最近公共祖先）

IP云
IP云V管理员/7 阅读
06/25
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

Description

Farmer John's cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ's distance queries as quickly as possible!

Input

  • Lines 1..1+M: Same format as "Navigation Nightmare"

  • Line 2+M: A single integer, K. 1 <= K <= 10,000

  • Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms.

Output

  • Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance.

Sample Input

7 6

1 6 13 E

6 3 9 E

3 5 7 S

4 1 3 N

2 4 20 W

4 7 2 S

3

1 6

1 4

2 6

Sample Output

13

3

36

Hint

Farms 2 and 6 are 20+3+13=36 apart.

分析：

要求的是任意两个农场之间的距离，题目上虽然给出了路的方向，但是这对于解题来说没有影响，可以看作无向图。并且两个节点之间至多有1条路，根据数据建图一定是一颗树。所以我们可以先把任一节点作为根节点，用深搜获取每个节点到根节点的距离，然后用Tarjan算法求最近公共祖先以及两点间的距离。

具体实现时深搜求距离和Tarjan算法求最近公共祖先可以同时进行，由于储存点的时候既要方便遍历与某节点相邻的所有节点，又要存储边权，同时最好能直接通过下标来访问数据。一般的结构体或者vector数组就不好用了。这里采用了“前向星”的数据结构。

Tarjan算法：

对于新搜索到的一个节点，首先创建由这个节点构成的集合，再对当前结点的每个子树进行搜索，每搜索完一棵子树，则可以确定子树内的LCA询问都已解决。其他的LCA询问的结果必然在这个子树之外，这时把子树所形成的集合与前节点的集合合并，并将当前节点设为这个集合的祖先。之后继续索搜下一刻子树，直到当前节点的所有子树搜索完毕。这时把当前节点也设为已被检查过的，同时可以处理有关当前节点的lCA询问，如果有一个从当前节点到节点v的询问，且v已被检查过，则由于进行的是深度优先搜索，当前节点与v的最近公共祖先一定还没有检查，而这个最近公共祖先的包含v的子树一定搜索过了，那么这个最近公共祖先一定是v所在集合的祖先。

即对于每个节点u：

1.建立以u为代表元素的集合

2.遍历与u相连的节点v，如果没有被访问过，对于v使用Tarjan算法，结束后，将v的集合并入u的集合。

3.对于与u有关的询问(u,v)，如果v被访问过，则结果就是v所在集合的代表元素。

递归求节点i到根节点的距离时，公式为：节点i对应起点到根节点的距离 + 起点到i的距离。对于所要求的两点间的距离公式为：两点到根节点的距离和 - 2 * 两点的最近公共祖先到根节点的距离。

代码：

#include<stdio.h>
#include<string.h>
#define MAX 80005int id,iq; //分别记录存储的点和询问的个数
int f[MAX],vis[MAX],dis[MAX]; //dis[i]记录根节点到i的距离
//head[i]记录以i为起点的第一条边的下标，qhead类似
int head[MAX],qhead[MAX];struct node
{ //前向星
int w; //两点间权值
int to; //终点
int next; //和to起点相同的下一条边的存储下标
} edge[MAX],que[MAX];void add_edge(int u,int v,int w)
{ //加点
edge[id].to=v;
edge[id].w=w;
edge[id].next=head[u];
head[u]=id++;
edge[id].to=u;
edge[id].w=w;
edge[id].next=head[v];
head[v]=id++;
}void add_que(int u,int v)
{ //加询问
que[iq].to=v;
que[iq].next=qhead[u];
qhead[u]=iq++;
que[iq].to=u;
que[iq].next=qhead[v];
qhead[v]=iq++;
}void init(int n)
{ //并查集的初始化函数
int i;
for(i=0;i<=n;i++) f[i]=i;
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
memset(head,-1,sizeof(head)); //head初始化为-1，表示无下一条边
memset(qhead,-1,sizeof(qhead));
}int find(int x)
{ //并查集的压缩路径版查找函数
if(x!=f[x]) f[x]=find(f[x]);
return f[x];
}void Tarjan(int root)
{
int i;
vis[root]=1;
f[root]=root;
for(i=head[root];i!=-1;i=edge[i].next)
{ //不断搜索以当前顶点为起点的节点
if(!vis[edge[i].to])
{
//根节点到终点的距离=根节点到起点的距离 + 边权
dis[edge[i].to]=dis[root]+edge[i].w;
Tarjan(edge[i].to);
f[edge[i].to]=root;
}
}
for(i=qhead[root];i!=-1;i=que[i].next)
{ //查询和当前节点有关的询问
if(vis[que[i].to])
{
//两点间距离为两点到根节点的距离和 - 两倍的最近总共祖先到根节点距离
que[i].w=dis[root]+dis[que[i].to]-2*dis[find(que[i].to)];
que[i^1].w=que[i].w; //第i和i+1的结果相同（i为偶数）
}
}
}int main()
{
int i,t,n,m,k,u,v,w;
scanf("%d%d",&n,&m); //顶点数和边数
init(n);
id=0;
for(i=0;i<m;i++)
{
scanf("%d%d%d%*c%*c",&u,&v,&w); //两节点及其之间的权值
add_edge(u,v,w);
}
scanf("%d",&k); //询问数
iq=0;
for(i=0;i<k;i++)
{
scanf("%d%d",&u,&v);
add_que(u,v);
}
Tarjan(1); //选节点1作为根节点
for(i=0;i<iq;i+=2) printf("%d\n",que[i].w);
return 0;
}

POJ 1986 Distance Queries （Tarjan算法求最近公共祖先）的更多相关文章

  1. tarjan算法求最近公共祖先

    tarjian算法 LCA: LCA(Least Common Ancestor),顾名思义,是指在一棵树中,距离两个点最近的两者的公共节点.也就是说,在两个点通往根的道路上,肯定会有公共的节点,我们 ...

  2. POJ 1986 Distance Queries &sol; UESTC 256 Distance Queries &sol; CJOJ 1129 【USACO】距离咨询（最近公共祖先）

    POJ 1986 Distance Queries / UESTC 256 Distance Queries / CJOJ 1129 [USACO]距离咨询(最近公共祖先) Description F ...

  3. POJ&period;1986 Distance Queries &lpar; LCA 倍增 &rpar;

    POJ.1986 Distance Queries ( LCA 倍增 ) 题意分析 给出一个N个点,M条边的信息(u,v,w),表示树上u-v有一条边,边权为w,接下来有k个询问,每个询问为(a,b) ...

  4. POJ 1986 Distance Queries LCA两点距离树

    标题来源:POJ 1986 Distance Queries 意甲冠军:给你一棵树 q第二次查询 每次你问两个点之间的距离 思路:对于2点 u v dis(u,v) = dis(root,u) + d ...

  5. POJ 1986 Distance Queries 【输入YY &amp&semi;&amp&semi; LCA（Tarjan离线）】

    任意门:http://poj.org/problem?id=1986 Distance Queries Time Limit: 2000MS   Memory Limit: 30000K Total ...

  6. POJ 1986 Distance Queries &lpar;最近公共祖先，tarjan&rpar;

    本题目输入格式同1984,这里的数据范围坑死我了!!!1984上的题目说边数m的范围40000,因为双向边,我开了80000+的大小,却RE.后来果断尝试下开了400000的大小,AC.题意:给出n个 ...

  7. POJ 1986 Distance Queries（Tarjan离线法求LCA）

    Distance Queries Time Limit: 2000MS   Memory Limit: 30000K Total Submissions: 12846   Accepted: 4552 ...

  8. POJ - 1986 Distance Queries（离线Tarjan算法）

    1.一颗树中,给出a,b,求最近的距离.(我没考虑不联通的情况,即不是一颗树的情况) 2.用最近公共祖先来求, 记下根结点到任意一点的距离dis[],这样ans = dis[u] + dis[v] - ...

  9. POJ 1986 - Distance Queries - &lbrack;LCA模板题&rsqb;&lbrack;Tarjan-LCA算法&rsqb;

    题目链接:http://poj.org/problem?id=1986 Description Farmer John's cows refused to run in his marathon si ...

随机推荐

  1. EXP&sol;IMP迁移案例，IMP遭遇导入表的表空间归属问题

    生产环境: 源数据库:Windows Server + Oracle 11.2.0.1 目标数据库:SunOS + Oracle 11.2.0.3 1.确认迁移需求:源数据库cssf 用户所有表和数据 ...

  2. 【转】Linux下如何清除系统日志

    使用过Windows的人都知道,在使用windows系统的过程中系统会变得越来越慢.而对于Windows下饱受诟病的各种垃圾文件都需要自己想办法删除,不然系统将会变得越来越大,越来越迟钝!window ...

  3. 为什么我要称自己为Javascript程序员

    Aaron Griffin写了一篇精彩的牢骚文章,主要是关于各种框架和它们能把程序员从主要业务编程中抽离出来的功能特征.概括一下他的主要论点,当你成为了一个“Rails程序员”,你使用的是一种易于理解 ...

  4. oracle查询和断开用户session

    select sid,serial#,username from v$session where username='user_name';alter system kill session 'sid ...

  5. Socket 理解

    TCP/IP要想理解socket首先得熟悉一下TCP/IP协议族, TCP/IP(Transmission Control Protocol/Internet Protocol)即传输控制协议/网间协 ...

  6. scss实现不同方向的三角

    //定义一个三角的函数 实现不同方向的三角加兼容ie6//第一个参数传入方向//第二个参数传入大小//第三个参数传入颜色//注意:传入参数中间必须逗号分隔@mixin triangle($x, $y: ...

  7. netty开发教程（一）

    Netty介绍 Netty is an asynchronous event-driven network application framework  for rapid development o ...

  8. k64 datasheet学习笔记21--Direct Memory Access Multiplexer &lpar;DMAMUX&rpar;

    0.前言 本章主要介绍DMA MUX的相关内容 1.简介 1.1 概述 用来路由DMA源到16路DMA通道: 1.2 特性 1.52个外设slot和10个常开slot可以路由到16路DMA通道 2.1 ...

  9. 解决centos 7&period;5安装openvpn，mirrors&period;163&period;com提示没有可用软件包openvpn、easy-rsa问题

    提示: yum install openvpn 已加载插件:fastestmirror Loading mirror speeds from cached hostfile * base: mirro ...

  10. Java知多少（31）static关键字以及Java静态变量和静态方法

    static 修饰符能够与变量.方法一起使用,表示是“静态”的. 静态变量和静态方法能够通过类名来访问,不需要创建一个类的对象来访问该类的静态成员,所以static修饰的成员又称作类变量和类方法.静态 ...