poj 1986 Distance Queries

点击打开链接poj 1986

思路：LCA+Tarjan离线算法+并查集

分析：
1 LCA指的是一棵有根树上两个点的最近公共祖先，或者指的是图上两个点的最短路径。
2 这一题的边数最大40000，还有k（k<=10000）次询问，如果利用最短路的算法肯定TLE。所以这个时候我们选择LCA，假设dis[x]是x到根节点的路径长度，那么(i , j)两点的最短路径为dis[i]+dis[j]-2*dis[LCA(i , j)];LCA(i , j)指的是i，j的最近公共祖先。
3 由于输入的是一个无向图，这个时候根节点是不固定的，所以保存的时候注意保存两次。然后只要随便选取一个作为根节点进行LCA即可（习惯把1作为根节点）
4 使用的是邻阶表存储无向图，注意数组的大小，不然会RE

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 100010

int n , m , k;
int ancestor[MAXN];
int father[MAXN];
int first[MAXN];
int next[MAXN];
int dis[MAXN];
int vis[MAXN];/*标记点是否被处理过*/
vector<int>v[MAXN];
struct Edge{
   int x; 
   int y;
   int value;
   int ans;
}e[MAXN] , q[MAXN];/*保存读入的边和询问的边*/

/*初始化*/
void init(){
   for(int i = 1 ; i <= n ; i++){
      father[i] = i;
      v[i].clear();
   }
   memset(ancestor , 0 , sizeof(ancestor));
   memset(first , -1 , sizeof(first));
   memset(next , -1 , sizeof(next));
   memset(dis , 0 , sizeof(dis));
   memset(vis , 0 , sizeof(vis));
}

/*并查集的查找*/
int find_Set(int x){
   if(x != father[x])
     father[x] = find_Set(father[x]);
   return father[x];
}

/*并查集的合并*/
void union_Set(int x , int y){
    int root_x = find_Set(x);
    int root_y = find_Set(y);
    father[root_x] = root_y;
}

/*Tarjan算法*/
void LCA(int u){
    ancestor[u] = u;
    vis[u] = 1;/*标记为处理过*/
    for(int i = first[u] ; i != -1 ; i = next[i]){
       if(!vis[e[i].y]){/*找到没被处理过的点*/
           dis[e[i].y] = dis[u] + e[i].value;/*更新dis数组*/
           LCA(e[i].y);/*继续搜索子树*/
           union_Set(e[i].y , u);/*合并*/
           ancestor[find_Set(e[i].y)] = u;/*当前节点为子树的祖先*/
       }
    }
    /*处理和u 和 v[u][i]有关的询问*/
    for(int i = 0 ; i < v[u].size() ; i++){
       if(vis[v[u][i]]){
          for(int j = 0 ; j < k ; j++){
             if(q[j].x == u && q[j].y == v[u][i] || q[j].x == v[u][i] && q[j].y == u)
               q[j].ans = father[find_Set(v[u][i])];
          }
       }
    }
}

int main(){
    char c;
    while(scanf("%d%d" , &n , &m) != EOF){
        init();
        for(int i = 0 ; i < m ; i++){
           scanf("%d %d %d %c" , &e[i].x , &e[i].y , &e[i].value , &c);
           /*邻阶表存储无向图*/
           e[i+m].x = e[i].y;
           e[i+m].y = e[i].x;
           e[i+m].value = e[i].value;
        
           next[i] = first[e[i].x];
           first[e[i].x] = i;
           next[i+m] = first[e[i+m].x];
           first[e[i+m].x] = i+m;
        }
        scanf("%d" , &k);
        for(int i = 0 ; i < k ; i++){
           scanf("%d%d" , &q[i].x , &q[i].y);
           v[q[i].x].push_back(q[i].y);
           v[q[i].y].push_back(q[i].x);
        }
        LCA(1);/*1作为根节点求LCA*/
        for(int i = 0 ; i < k ; i++){
           int tmp = dis[q[i].x]+dis[q[i].y]-2*dis[q[i].ans];       
           printf("%d\n" , tmp);
        }
    }
    return 0;
}