HDU 4297 One and One Story (LCA>RMQ)

题意就是找森林里的LCA，构图完成了这个题基本就没问题了。

已知的是所给的图上是可能有环的。那么可以对这些环进行类似缩点的操作（当然不是tarjan），设一个虚拟根0点，链接环上的每一个点。

对于不在环上的点直接加无向边建树就行。

预处理出每个环包含哪些点，每个环中点的顺序（环是有方向的）

对得到的树进行LCA到RMQ的转化，同时记录当前点到0点的距离，O(nlogn)的时间预处理，O(1)的时间求LCA。

分几种情况：

1、两点的LCA是环上的同一个点，这个直接出结果（根据距离）

2、两点的LCA在同一个环的不同点上，这个要根据环的方向判断一下优弧劣弧。

3、两点的LCA不再同一环上。直接输出-1 -1;

详见代码吧。。。很搓很搓的写了6K+。。。经此一役，DSU， RMQ，LAC的模板都有了。。。

View Code

  1 //#pragma comment(linker,"/STACK:1024000000,1024000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <vector>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <string>
  9 #include <set>
 10 #include <functional>
 11 #include <numeric>
 12 #include <sstream>
 13 #include <stack>
 14 
 15 #define CL(arr, val)    memset(arr, val, sizeof(arr))
 16 #define REP(i, n)       for((i) = 0; (i) < (n); ++(i))
 17 #define FOR(i, l, h)    for((i) = (l); (i) <= (h); ++(i))
 18 #define FORD(i, h, l)   for((i) = (h); (i) >= (l); --(i))
 19 #define L(x)    (x) << 1
 20 #define R(x)    (x) << 1 | 1
 21 #define MID(l, r)   (l + r) >> 1
 22 #define Min(x, y)   x < y ? x : y
 23 #define Max(x, y)   x < y ? y : x
 24 #define E(x)    (1 << (x))
 25 #define iabs(x) (x) < 0 ? -(x) : (x)
 26 #define OUT(x)  printf("%I64d\n", x)
 27 #define lowbit(x)   (x)&(-x)
 28 #define Read()    freopen("data.in", "r", stdin)
 29 #define Write()   freopen("data.out", "w", stdout);
 30 
 31 const double eps = 1e-8;
 32 typedef long long LL;
 33 const int inf = ~0u>>2;
 34 
 35 using namespace std;
 36 
 37 const int N = 500010;
 38 int n;
 39 
 40 struct node {
 41     int to;
 42     int next;
 43     node() {}
 44 } g[N<<2];
 45 
 46 int head[N], t;
 47 class Graph {    //树。。
 48 public:
 49     void init() {
 50         CL(head, -1); t = 0;
 51     }
 52     void add(int u, int v) {
 53         g[t].to = v; g[t].next = head[u]; head[u] = t++;
 54     }
 55 }G;
 56 
 57 
 58 int parent[N];
 59 class DSU {    //并查集
 60 public:
 61     void init(int n) {
 62         for(int i = 0; i <= n; ++i) parent[i] = i;
 63     }
 64     void union_set(int a, int b) {
 65         parent[a] = b;
 66     }
 67     int find(int x) {
 68         int k, j;
 69         k = x;
 70         while(x != parent[x])   x = parent[x];
 71 
 72         while(k != x) {
 73             j = parent[k];
 74             parent[k] = x;
 75             k = j;
 76         }
 77         return x;
 78     }
 79 }DSU;
 80 
 81 int D[N], E[N<<1], R[N<<1];
 82 int Min[N<<1][20];
 83 
 84 class RMQ {    //RMQ
 85 public:
 86     void build(int n) {
 87         int i, j, m;
 88         for(i = 1; i <= n; ++i) Min[i][0] = i;
 89         m = int(log(double(n))/log(2.0));
 90         FOR(j, 1, m) {
 91             FOR(i, 1, n - (1<<j) + 1) {
 92                 if(D[Min[i][j-1]] < D[Min[i+(1<<(j-1))][j-1]]) {
 93                     Min[i][j] = Min[i][j-1];
 94                 } else {
 95                     Min[i][j] = Min[i+(1<<(j-1))][j-1];
 96                 }
 97 
 98             }
 99         }
100     }
101 
102     int query(int s, int e) {
103         int k = log(double(e - s + 1))/log(2.0);
104         if(D[Min[s][k]] < D[Min[e-(1<<k) + 1][k]])   return  Min[s][k];
105         else    return Min[e-(1<<k) + 1][k];
106     }
107 } Q;
108 
109 int dis[N], root[N], cir[N];
110 int nxt[N];
111 int cnt;
112 bool vis[N];
113 
114 class LCA {    //LCA
115 public:
116     void init() {
117         CL(D, 0); CL(dis, 0);
118         CL(E, 0); CL(R, 0);
119         CL(vis, 0); cnt = 0;
120     }
121     void dfs(int t, int dep) {
122         D[++cnt] = dep;
123         E[cnt] = t;
124 
125         if(!vis[t]) {
126             R[t] = cnt;
127             vis[t] = true;
128         }
129         for(int i = head[t]; i != -1; i = g[i].next) {
130             if(vis[g[i].to])    continue;
131 
132             dis[g[i].to] = dis[t] + 1;
133             dfs(g[i].to, dep + 1);
134 
135             D[++cnt] = dep;
136             E[cnt] = t;
137         }
138     }
139     /*
140     void display() {
141         int i;
142         for(i = 1; i <= cnt; ++i)
143             printf("%-3d", i);
144         cout << endl;
145         for(i = 1; i <= cnt; ++i)
146             printf("%-3d", D[i]);
147         cout << endl;
148         for(i = 1; i <= cnt; ++i)
149             printf("%-3d", E[i]);
150         cout << endl;
151         for(i = 1; i <= n; ++i) {
152             printf("%d ", R[i]);
153         }
154         cout << endl;
155     }
156     */
157     void solve() {
158         init();
159         dfs(0, 0);
160         Q.build(cnt);
161     }
162 
163     int query(int x, int y) {
164         x = R[x]; y = R[y];
165         if(x > y)   swap(x, y);
166        // printf("%d\n", Q.query(x, y));
167         return E[Q.query(x, y)];
168     }
169 }LCA;
170 
171 void rdfs(int u, int r) {    //把非环上点的根节点都处理出来。
172     root[u] = r;
173     for(int i = head[u]; i != -1; i = g[i].next) {
174         if(root[g[i].to] == -1) {
175             rdfs(g[i].to, r);
176         }
177     }
178 }
179 
180 int num;
181 int pos[N], len[N];    //每个点在环中的位置，每个环的长度
182 
183 void deal() {    //预处理环的情况
184     CL(cir, -1);  CL(pos, -1);
185     CL(len, 0);
186 
187     DSU.init(n);
188     int i, j, cnt, x, y;
189     num = 0;
190     for(i = 1; i <= n; ++i) {
191         x = DSU.find(i);
192         y = DSU.find(nxt[i]);
193         if(x == y)  cir[i] = ++num;
194         DSU.union_set(x, y);
195     }
196 
197     for(i = 1; i <= n; ++i) {
198         if(cir[i] != -1) {
199             j = nxt[i];
200             cnt = 0;
201             pos[i] = ++cnt;
202             root[i] = i;
203             while(j != i) {
204                 pos[j] = ++cnt;
205                 root[j] = j;
206                 cir[j] = cir[i];
207                 j = nxt[j];
208             }
209             len[cir[i]] = cnt;
210         }
211     }
212 }
213 
214 
215 int main() {
216     //Read();
217 
218     int i, k, p, ra, rb;
219     int a, b, x1, y1, x2, y2;
220     int ansx, ansy;
221     while(~scanf("%d%d", &n, &k)) {
222         CL(root, -1);
223         for(i = 1; i <= n; ++i) scanf("%d", nxt + i);
224         deal();
225         G.init();
226         for(i = 1; i <= n; ++i) {
227             if(root[i] != i) {
228                 G.add(i, nxt[i]);
229                 G.add(nxt[i], i);
230                 //printf("*%d %d\n", i, nxt[i]);
231             }
232         }
233         for(i = 1; i <= n; ++i) {
234             if(root[i] == i) {
235                 rdfs(i, i);
236                 G.add(0, i);
237                 G.add(i, 0);
238                 //printf("*%d %d\n", 0, nxt[i]);
239             }
240         }
241         LCA.solve();
242         //LCA.display();
243         while(k--) {
244             scanf("%d%d", &a, &b);
245             p = LCA.query(a, b);
246             if(p != 0) {
247                 printf("%d %d\n", dis[a] - dis[p], dis[b] - dis[p]);
248                 continue;
249             }
250             ra = root[a], rb = root[b];
251             if(cir[ra] != cir[rb])  {printf("-1 -1\n"); continue;}
252             x1 = x2 = dis[a] - 1;
253             y1 = y2 = dis[b] - 1;
254             //A沿着环的方向靠近B
255             if(pos[ra] < pos[rb])   x1 += pos[rb] - pos[ra];
256             else    x1 += len[cir[ra]] - (pos[ra] - pos[rb]);
257             //B沿着环的方向靠近A
258             if(pos[rb] < pos[ra])   y2 += pos[ra] - pos[rb];
259             else    y2 += len[cir[rb]] - (pos[rb] - pos[ra]);
260             /*
261             printf("(x1, y1) = (%d, %d)\n", x1, y1);
262             printf("(x2, y2) = (%d, %d)\n", x2, y2);
263             */
264             if(max(x1, y1) < max(x2, y2))   ansx = x1, ansy = y1;
265             else if(max(x1, y1) > max(x2, y2))  ansx = x2, ansy = y2;
266             else {
267                 if(min(x1, y1) < min(x2, y2))   ansx = x1, ansy = y1;
268                 else    if(min(x1, y1) > min(x2, y2))   ansx = x2, ansy = y2;
269                 else {
270                     if(x1 >= y1)    ansx = x1, ansy = y1;
271                     else    ansx = x2, ansy = y2;
272                 }
273             }
274             printf("%d %d\n", ansx, ansy);
275         }
276     }
277     return 0;
278 }