hdu2586(lca模板 / tarjan离线 + RMQ在线)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2586

题意: 给出一棵 n 个节点的带边权的树, 有 m 个形如 x y 的询问, 要求输出所有 x, y节点之间的最短距离.

思路: dis[i] 存储 i 节点到根节点的最短距离, lca 为 x, y 的最近公共祖先, 那么 x, y 之间的最短距离为: dis[x] + dis[y] - 2 * dis[lca] .

解法1: tarjan离线算法

关于该算法

 Tarjan(u)//marge和find为并查集合并函数和查找函数

 {

     for each(u,v)    //访问所有u子节点v

     {

         Tarjan(v);        //继续往下遍历

         marge(u,v);    //合并v到u上

         标记v被访问过;

     }

     for each(u,e)    //访问所有和u有询问关系的e

     {

         如果e被访问过;

         u,e的最近公共祖先为find(e);

     }

 }

详解见: http://www.cnblogs.com/ECJTUACM-873284962/p/6613379.html

代码:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 const int MAXN = 4e4 + ;

 struct node{

     int u, v, w, lca, next;

 }edge1[MAXN << ], edge2[];//edge1记录树, edge2记录询问

 int vis[MAXN], pre[MAXN], dis[MAXN];//vis[i]标记i是否已经搜索过, pre[i]记录i的根节点, dis[i]记录i到根节点的距离

 int head1[MAXN], head2[MAXN], ance[MAXN], ip1, ip2;

 void init(void){

     memset(vis, , sizeof(vis));

     memset(dis, , sizeof(dis));

     memset(head1, -, sizeof(head1));

     memset(head2, -, sizeof(head2));

     ip1 = ip2 = ;

 }

 void addedge1(int u, int v, int w){//前向星

     edge1[ip1].v = v;

     edge1[ip1].w = w;

     edge1[ip1].next = head1[u];

     head1[u] = ip1++;

 }

 void addedge2(int u, int v){

     edge2[ip2].u = u;

     edge2[ip2].v = v;

     edge2[ip2].lca = -;

     edge2[ip2].next = head2[u];

     head2[u] = ip2++;

 }

 int find(int x){

     return pre[x] == x ? x : pre[x] = find(pre[x]);

 }

 void jion(int x, int y){

     x = find(x);

     y = find(y);

     if(x != y) pre[y] = x;

 }

 void tarjan(int u){

     vis[u] = ;

     ance[u] = pre[u] = u;

     for(int i = head1[u]; i != -; i = edge1[i].next){

         int v = edge1[i].v;

         int w = edge1[i].w;

         if(!vis[v]){

             dis[v] = dis[u] + w;

             tarjan(v);

             jion(u, v);

         }

     }

     for(int i = head2[u]; i != -; i = edge2[i].next){

         int v = edge2[i].v;

         if(vis[v]) edge2[i].lca = edge2[i ^ ].lca = ance[find(v)];

     }

 }

 int main(void){

     int t, n, m, x, y, z;

     scanf("%d", &t);

     while(t--){

         init();

         scanf("%d%d", &n, &m);

         for(int i = ; i < n; i++){

             scanf("%d%d%d", &x, &y, &z);

             addedge1(x, y, z);

             addedge1(y, x, z);

         }

         for(int i = ; i < m; i++){

             scanf("%d%d", &x, &y);

             addedge2(x, y);

             addedge2(y, x);

         }

         dis[] = ;

         tarjan();

         for(int i = ; i < m; i++){

             int cc = i << ;

             int u = edge2[cc].u;

             int v = edge2[cc].v;

             int lca = edge2[cc].lca;

             printf("%d\n", dis[u] + dis[v] -  * dis[lca]);

         }

     }

     return ;

 }

解法2: lca转RMQ

关于该算法

ver[] 存储树的 dfs 路径

first[u] 为顶点 u 在 ver 数组中第一次出现时的下标

deep[indx] 为顶点 ver[indx] 的深度

对于求 x, y 的 lca, 先令 l = first[x], r = first[y], 即 l, r 分别为 x, y 第一次在 ver 数组中出现时对应的下标

在 deep[] 数组中找到区间 [l, r] 中的最小值, 其下标对应的 ver 值即为 x, y 的 lca. (区间最值可以用 RMQ 处理)

详解见: http://blog.csdn.net/u013076044/article/details/41870751

代码:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 using namespace std;

 const int MAXN = 4e4 + ;

 struct node{

     int v, w, next;

 }edge[MAXN << ];

 int dp[MAXN << ][]; //dp[i][j]存储deep数组中下标i开始长度为2^j的子串中最小值的下标

 int first[MAXN], ver[MAXN << ], deep[MAXN << ];

 int vis[MAXN], head[MAXN], dis[MAXN], ip, indx;

 inline void init(void){

     memset(vis, , sizeof(vis));

     memset(head, -, sizeof(head));

     ip = ;

     indx = ;

 }

 void addedge(int u, int v, int w){

     edge[ip].v = v;

     edge[ip].w = w;

     edge[ip].next = head[u];

     head[u] = ip++;

 }

 void dfs(int u, int h){

     vis[u] = ; //标记已搜索过的点

     ver[++indx] = u; //记录dfs路径

     first[u] = indx; //记录顶点u第一次出现时对应的ver数组的下标

     deep[indx] = h; //记录ver数组中对应下标的点的深度

     for(int i = head[u]; i != -; i = edge[i].next){

         int v = edge[i].v;

         if(!vis[v]){

             dis[v] = dis[u] + edge[i].w;

             dfs(v, h + );

             ver[++indx] = u;

             deep[indx] = h;

         }

     }

 }

 void ST(int n){

     for(int i = ; i <= n; i++){

         dp[i][] = i;

     }

     for(int j = ; ( << j) <= n; j++){

         for(int i = ; i + ( << j) -  <= n; i++){

             int x = dp[i][j - ], y = dp[i + ( << (j - ))][j - ];

             dp[i][j] = deep[x] < deep[y] ? x : y;

         }

     }

 }

 int RMQ(int l, int r){

     int len = log2(r - l + );

     int x = dp[l][len], y = dp[r - ( << len) + ][len];

     return deep[x] < deep[y] ? x : y;

 }

 int LCA(int x, int y){

     int l = first[x], r = first[y];

     if(l > r) swap(l, r);

     int pos = RMQ(l, r);

     return ver[pos];

 }

 int main(void){

     int t, n, m, x, y, z;

     scanf("%d", &t);

     while(t--){

         init();

         scanf("%d%d", &n, &m);

         for(int i = ; i < n; i++){

             scanf("%d%d%d", &x, &y, &z);

             addedge(x, y, z);

             addedge(y, x, z);

         }

         dis[] = ;

         dfs(, );

         ST( * n - );

         for(int i = ; i < m; i++){

             scanf("%d%d", &x, &y);

             int lca = LCA(x, y);

             printf("%d\n", dis[x] + dis[y] -  * dis[lca]);

         }

     }

     return ;

 }

巴特西

hdu2586(lca模板 / tarjan离线 + RMQ在线)

最新文章

热门文章