POJ 1986 Distance Queries——LCA

POJ 1986 Distance Queries——LCA

题意：

树上两点间的最近距离

思路：

Tarjan求LCA， dis[u]+dis[v]-dis[lca(u, v)]即可

边表居然比vector快5倍。。。绝了

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;char ch[100];int n, m, q;int tot1, tot2, head1[maxn], head2[maxn];struct Edge { int to, x, next; } edge1[maxn], edge2[maxn];void addedge1(int u, int v, int dis) { edge1[++tot1].to = v; edge1[tot1].x = dis; edge1[tot1].next = head1[u]; head1[u] = tot1;}void addedge2(int u, int v, int id) { edge2[++tot2].to = v; edge2[tot2].x = id; edge2[tot2].next = head2[u]; head2[u] = tot2;}struct Ans { int u, v, lca; } ans[maxn];int dis[maxn], vis[maxn];int fa[maxn];void init() { tot1 = tot2 = 0; for (int i = 1; i <= n; i++) head1[i] = head2[i] = -1; dis[1] = 0; for (int i = 1; i <= n; i++) vis[i] = 0, fa[i] = i;}int query(int x) { return (fa[x] == x ? x : fa[x] = query(fa[x])); }void dfs(int u, int p) { vis[u] = 1; for (int i = head1[u]; ~i; i = edge1[i].next) { int v = edge1[i].to, d = edge1[i].x; if (v == p) continue; dis[v] = dis[u] + d; dfs(v, u); fa[v] = u; } for (int i = head2[u]; ~i; i = edge2[i].next) { int v = edge2[i].to, id = edge2[i].x; if (!vis[v]) continue; ans[id].lca = query(v); }}int main() { while (~scanf("%d%d", &n, &m)) { init(); int u, v, d; while (m--) { scanf("%d%d%d%s", &u, &v, &d, ch); addedge1(u, v, d); addedge1(v, u, d); } scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d%d", &u, &v); addedge2(u, v, i); addedge2(v, u, i); ans[i].u = u, ans[i].v = v, ans[i].lca = 1; } dfs(1, -1); for (int i = 1; i <= q; i++) { printf("%d\n", dis[ans[i].u] + dis[ans[i].v] - 2*dis[ans[i].lca]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。