POJ 1470 Closest Common Ancestors

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

LCA模板题，但要注意scanf的用法。

题目链接POJ 1470

详解请见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
120
121
122
123
124
125
126
127
128
129
130
#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>
#define maxn 1005
using namespace std;
struct node
{
        int x;
};
vector<node> V[maxn];
int E[maxn * 2], D[maxn * 2], first[maxn],counter[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));
        for (int i = 1; i <= n; i++)
        {
                V[i].clear();
        }
        int k;
        node tmp;
        for (int i = 0; i < n; i++)
        {
                scanf("%d:(%d)",&m,&k);
                while(k--)
                {
                        int a;
                        scanf("%d",&a);
                        tmp.x = a;
                        V[m].push_back(tmp);
                        tmp.x = m;
                        V[a].push_back(tmp);
                        root[a] = 1;
                }
        }
        for (int i = 1; i <= n; i++)
                if (root[i] == 0)
                {
                        st = i;
                        break;
                }
}
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;
                        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 ()
{
        while(scanf("%d", &n)!=EOF)
        {
                init();
                memset(counter,0,sizeof(counter));
                dfs(st, 0);
                ST(top);
                int x, y;
                int o;
                cin>>o;
                while(o--)
                {
                        scanf(" (%d %d)", &x, &y);//注意双引号后的空格不能少
                        int a = first[x], b = first[y];
                        if (a > b)
                        {
                                swap(a, b);
                        }
                        int pos = RMQ(a, b);
                        counter[E[pos]]++;
                }
                for(int i=1;i<=maxn;i++)
                {
                        if(counter[i]!=0)
                        {
                                printf("%d:%d\n",i,counter[i]);
                        }
                }
        }
        return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！