Time Limit: 1 Second Memory Limit: 32768 KB
Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams everywhere. Now, Cerror finds out that the main reason of them is the poor design of the roads distribution, and he want to change this situation.
In order to achieve this project, he divide the city up to N regions which can be viewed as separate points. He thinks that the best design is the one that connect all region with shortest road, and he is asking you to check some of his designs.
Now, he gives you an acyclic graph representing his road design, you need to find out the shortest path to connect some group of three regions.
Input
The input contains multiple test cases! In each case, the first line contian a interger N (1 < N < 50000), indicating the number of regions, which are indexed from 0 to N-1. In each of the following N-1 lines, there are three interger Ai, Bi, Li (1 < Li < 100) indicating there's a road with length Li between region Ai and region Bi. Then an interger Q (1 < Q < 70000), the number of group of regions you need to check. Then in each of the following Q lines, there are three interger Xi, Yi, Zi, indicating the indices of the three regions to be checked.
Process to the end of file.
Output
Q lines for each test case. In each line output an interger indicating the minimum length of path to connect the three regions.
Output a blank line between each test cases.
Sample Input
4 0 1 1 0 2 1 0 3 1 2 1 2 3 0 1 2 5 0 1 1 0 2 1 1 3 1 1 4 1 2 0 1 2 1 0 3
Sample Output
3 2 2 2
题意:
给出结点数 N ,后给出 N - 1 条边。给出 Q 个询问,每个询问给出 3 个结点,输出这三点连通的最短距离。
思路:
LCA。因为 1 -> 2 + 2 -> 3 的距离等于 1 -> 3 的距离,所以将 3 个点间两两的距离求出后加和除以 2 即为答案。用 LCA 求出两两间点距离即可。输出的格式问题,每个 case 后输出一行空行,最后一组样例不需要有空行。所以用 temp 标记输出即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int VMAX = 50010; const int EMAX = VMAX * 2; int n, ind; int v[EMAX], fir[VMAX], next[EMAX], w[EMAX]; int cnt; int vs[VMAX * 2], dep[VMAX * 2], id[VMAX], dis[VMAX]; bool vis[VMAX]; int dp[VMAX * 2][25]; void init () { ind = cnt = 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) { id[x] = cnt; vs[cnt] = x; dep[cnt++] = d; vis[x] = 1; 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); vs[cnt] = x; dep[cnt++] = d; } } } void RMQ_init () { for (int i = 0; i < cnt; ++i) dp[i][0] = i; for (int j = 1; (1 << j) <= cnt; ++j) { for (int i = 0; i + (1 << j) < cnt; ++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 << (1 + len)) <= 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 Distance (int a, int b, int c) { int ab = LCA(a, b); int ac = LCA(a, c); int bc = LCA(b, c); int res = 0; res += dis[a] + dis[b] - 2 * dis[ab]; res += dis[a] + dis[c] - 2 * dis[ac]; res += dis[b] + dis[c] - 2 * dis[bc]; return res / 2; } int main() { int temp = 0; while (~scanf("%d", &n)) { if (temp) printf("\n"); temp = 1; init(); for (int i = 1; i <= n - 1; ++i) { int a, b, val; scanf("%d%d%d", &a, &b, &val); ++a; ++b; add_edge(a, b, val); add_edge(b, a, val); } dis[1] = 0; dfs(1, 0); RMQ_init(); int q; scanf("%d", &q); while (q--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); ++a, ++b, ++c; printf("%d\n", Distance(a, b, c)); } } return 0; }
相关推荐
很详细的LCA与RMQ计算过程的图例演示,以及他们之间的转换
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
算法学习
RMQ与LCA ACM必备RMQ与LCA ACM必备 RMQ与LCA ACM必备
1、 概述LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法
第一行有两个空格分隔的整数 N 和 Q 第一行有两个整数 N 和 M 第一行有三个整数 N、Q 和 S,用空格分隔 第一行有一个整数 N,接下来有 N 行,每一
a very good presentation, ideal for quick learning of some LCA and RMQ aproaches
原文来自于http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor。 翻译成中文。 LCA RMQ
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
该ppt讲了一种基于线段树的RMQ的ST算法问题和LCA算法,适合初学者用。
如“重新审阅LCA问题”中所述,这将使用“范围最小查询”实现LCA。 已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..))) indexs : 0, 1, 2, 3,...
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!
3.郭华阳《RMQ与LCA问题》.ppt
ACM中的RMQ和LCA问题 对一个区间的最小值询问,也可以是最大值
RMQ以及LCA:最近公共祖先 解析及P解法 (ZFrom Internet)
一份很不错RMQ与LCA问题的讲解,及其相互关系。推荐。
LCA 问题的解决及应用长沙市长郡中学 郭华阳目录【正文】1RMQ 与 LCA 问题的提出1一.LCA 问题的提出1RMQ 与 LCA 问题的可转化性2一.RM
算法文档无代码RMQ&LCA问题提取方式是百度网盘分享地址
倍增法介绍以及应用(RMQ、LCA)
算法合集之RMQ与LCA问题PPT学习教案.pptx