Distance Queries
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 9500 | Accepted: 3332 | |
Case Time Limit: 1000MS |
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.
* 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.
题意:
给出 N 和 M,代表 N 个节点,M 条边,后给出边信息,有 K 个询问,输出每个询问两点间的距离。
思路:
LCA。RMQ 的在线算法。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int VMAX = 40010; const int EMAX = VMAX * 5; int ind; int v[EMAX], fir[VMAX], next[EMAX], w[EMAX]; int ans; int id[VMAX], vs[VMAX * 2], dep[VMAX * 2], dis[VMAX]; bool vis[VMAX]; int dp[VMAX * 2][30]; void init () { ind = ans = 0; memset(fir, -1, sizeof(fir)); memset(vis, 0, sizeof(vis)); } void add_edge (int f, int t, int val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ++ind; } void dfs (int x, int d) { vis[x] = 1; id[x] = ans; dep[ans] = d; vs[ans++] = x; for (int e = fir[x]; e != -1; e = next[e]) { int V = v[e]; if (!vis[V]) { dis[V] = dis[x] + w[e]; dfs(V, d + 1); dep[ans] = d; vs[ans++] = x; } } } void RMQ_init () { for (int i = 0; i < ans; ++i) dp[i][0] = i; for (int j = 1; (1 << j) <= ans; ++j) { for (int i = 0; i + (1 << j) < ans; ++i) { int a = dp[i][j - 1]; int b = dp[i + (1 << (j - 1))][j - 1]; if (dep[a] < dep[b]) dp[i][j] = a; else dp[i][j] = b; } } } int RMQ (int L, int R) { int len = 0; while ((1 << (len + 1)) <= (R - L + 1)) ++len; int a = dp[L][len]; int b = dp[R - (1 << len) + 1][len]; if (dep[a] < dep[b]) return a; return b; } int LCA (int a, int b) { int L = min(id[a], id[b]); int R = max(id[a], id[b]); int node = RMQ(L, R); return vs[node]; } int main () { init(); int n, m; scanf("%d%d", &n, &m); while (m--) { int a, b, val; char c; scanf("%d%d%d %c", &a, &b, &val, &c); add_edge(a, b, val); add_edge(b, a, val); } dis[1] = 0; dfs(1, 1); RMQ_init(); int k; scanf("%d", &k); while (k--) { int a, b; scanf("%d%d", &a, &b); int c = LCA(a, b); printf("%d\n", dis[a] + dis[b] - 2 * dis[c]); } return 0; }
相关推荐
RMQ与LCA ACM必备RMQ与LCA ACM必备 RMQ与LCA ACM必备
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
最小公祖问题的算法。 如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..)))...
很详细的LCA与RMQ计算过程的图例演示,以及他们之间的转换
算法学习
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
该ppt讲了一种基于线段树的RMQ的ST算法问题和LCA算法,适合初学者用。
1、 概述LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法
a very good presentation, ideal for quick learning of some LCA and RMQ aproaches
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
一个很经典的论文,关于slca的论文,现在关于查询方面的知识,好多都是基于slca的
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
算法合集之RMQ与LCA问题PPT学习教案.pptx
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!
3.郭华阳《RMQ与LCA问题》.ppt
原文来自于http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor。 翻译成中文。 LCA RMQ
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
ACM中的RMQ和LCA问题 对一个区间的最小值询问,也可以是最大值
第一行有两个空格分隔的整数 N 和 Q 第一行有两个整数 N 和 M 第一行有三个整数 N、Q 和 S,用空格分隔 第一行有一个整数 N,接下来有 N 行,每一