Distance Queries
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 8642 | Accepted: 3036 | |
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 条无向边。后给出这 M 条边的两端点编号和距离和方位(方位可以无视)。后有 K 个询问,每个询问输出一个答案,输出这两个点的距离。
思路:
LCA(最近公共祖先)(倍增法)。预处理每个结点的深度值 和 根节点到每个节点的距离值 dis,求出 两个点的 LCA 后 d = dis [ A ] + dis [ B ] - 2 X dis [ LCA ] 即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int NMAX = 40005; const int EMAX = NMAX * 5; int ind, n, MAX_V; int fir[NMAX], next[EMAX], v[EMAX], w[EMAX]; int par[20][NMAX], dep[NMAX], dis[NMAX]; void add_edge(int f, int t, int val) { v[ind] = t; next[ind] = fir[f]; fir[f] = ind; w[ind] = val; ++ind; } void dfs(int i, int fa, int k, int d) { par[0][i] = fa; dep[i] = k; dis[i] = d; for (int e = fir[i]; e != -1; e = next[e]) { if (v[e] != fa) dfs(v[e], i, k + 1, d + w[e]); } } void init() { dfs(1, -1, 0, 0); for (int i = 0; i < MAX_V - 1; ++i) { for (int j = 1; j <= n; ++j) { if (par[i][j] < 0) par[i + 1][j] = -1; else par[i + 1][j] = par[i][ par[i][j] ]; } } } int lca(int f, int t) { if (dep[t] > dep[f]) { int a = f; f = t; t = a; } int dis = dep[f] - dep[t]; for (int i = 0; i < MAX_V; ++i) if ((dis >> i) & 1) f = par[i][f]; if (f == t) return f; for (int i = MAX_V - 1; i >= 0; --i) { if (par[i][f] != par[i][t]) { f = par[i][f]; t = par[i][t]; } } return par[0][f]; } int main() { int m; scanf("%d%d", &n, &m); memset(fir, -1, sizeof(fir)); ind = 0; MAX_V = 0; while ((1 << MAX_V) <= n) ++MAX_V; while (m--) { int a, b, num; char d; scanf("%d%d%d %c", &a, &b, &num, &d); add_edge(a, b, num); add_edge(b, a, num); } init(); int k; scanf("%d", &k); while (k--) { int f, t; scanf("%d%d", &f, &t); int ans = lca(f, t); printf("%d\n", dis[f] + dis[t] - 2 * dis[ans]); } return 0; }
相关推荐
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
RMQ与LCA ACM必备RMQ与LCA ACM必备 RMQ与LCA ACM必备
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
日立LCA电气图纸(K3500490).pdf
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
用户数据的读取方法,如何对LCA265显示器传输数据。
LCA 中文教程,内部资料--产品结构管理,还不错啊,可以看下
LCA生命周期评价,LCA生命周期评价课件,LCA生命周期评价PPT
数据泄密(泄露)防护(Data leakage prevention, DLP),又称为“数据丢失防护”(Data Loss prevention, DLP),有时也称为“信息泄漏防护”(Information leakage prevention, ILP)。数据泄密防护(DLP)是通过一定的...
LCA词汇复杂度分析软件 跟官网一毛一样 可以做成本地接口
很详细的LCA与RMQ计算过程的图例演示,以及他们之间的转换
一个很经典的论文,关于slca的论文,现在关于查询方面的知识,好多都是基于slca的
lca51仿真软件早期版本2.02版,不知是否有需要的。
SAS+proc lca浅类别分析安装程序
Tarjan应用LCA
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
算法学习
LCA系统中的数据状态控制以及数据升版操作规范
LCA系统 DB2数据库 表 修改数据状态
最近公共祖先(LCA),转化为 RMQ 用线段树解决