POJ 1986 Distance Queries

发表于   |   分类于   |     |   阅读次数

LCA模板题

题目链接POJ 1986

详解请见HDU 2586

附加AC代码

我用的是LCA-RMQ-ST算法。

LCA-RMQ-ST算法详解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define maxn 40005
struct node
{
        int x,l;
};
vector<node> V[maxn];
int E[maxn * 2], D[maxn * 2], first[maxn];
int vis[maxn], dist[maxn], n, m, top = 1, root[maxn], st;
int dp[30][maxn * 2];
void init()
{
        top = 1;
        memset(root, 0, sizeof(root));
        memset(vis, 0, sizeof(vis));
        scanf("%d %d", &n,&m);
        for (int i = 1; i <= n; i++)
        {
                V[i].clear();
        }
        int a, b,c;
        node tmp;
        for (int i = 0; i < m; i++)
        {
                char d;
                scanf(" %d %d %d %c", &a, &b,&c,&d);
                tmp.x = b;
                tmp.l=c;
                V[a].push_back(tmp);
                tmp.x = a;
                V[b].push_back(tmp);
                root[b] = 1;
        }
        for (int i = 1; i <= n; i++)
                if (root[i] == 0)
                {
                        st = i;
                        break;
                }
        dist[st]=0;
}
void dfs(int u, int dep)
{
        vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++;
        for (int i = 0; i < V[u].size(); i++)
                if (!vis[V[u][i].x])
                {
                        int v = V[u][i].x;
                        dist[v]=dist[u]+V[u][i].l;
                        dfs(v, dep + 1);
                        E[top] = u, D[top++] = dep;
                }
}
void ST(int num)
{
        for (int i = 1; i <= num; i++)
        {
                dp[0][i] = i;
        }
        for (int i = 1; i <= log2(num); i++)
                for (int j = 1; j <= num; j++)
                        if (j + (1 << i) - 1 <= num)
                        {
                                int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)];
                                if (D[a] < D[b])
                                {
                                        dp[i][j] = a;
                                }
                                else
                                {
                                        dp[i][j] = b;
                                }
                        }
}
int RMQ(int x, int y)
{
        int k = (int) log2(y - x + 1.0);
        int a = dp[k][x], b = dp[k][y - (1 << k) + 1];
        if (D[a] < D[b])
        {
                return a;
        }
        return b;
}
int main ()
{
        init();
        dfs(st, 0);
        ST(top);
        int x, y;
        int k;
        cin>>k;
        while(k--)
        {
                scanf("%d%d", &x, &y);
                int a = first[x], b = first[y];
                if (a > b)
                {
                        swap(a, b);
                }
                int pos = RMQ(a, b);
                printf("%d\n",dist[x]+dist[y]-2*dist[E[pos]]);
        }
        return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！