CUGB图论专场:G - Distance Queries(LCA Tarjan算法)

G - Distance Queries
Time Limit:2000MS     Memory Limit:30000KB     64bit IO Format:%I64d & %I64u

Description

Farmer John‘s cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ‘s distance queries as quickly as possible! 

Input

* Lines 1..1+M: Same format as "Navigation Nightmare" 

* Line 2+M: A single integer, K. 1 <= K <= 10,000 

* Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms. 

Output

* Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance. 

Sample Input

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6

Sample Output

13
3
36

Hint

Farms 2 and 6 are 20+3+13=36 apart. 

LCA Tarjan算法:-----------------------------------(以下为转载)-------------------------------------------------

还是要先说一下Tarjan算法的适用条件,那就是要离线算法,也就是要先输入完所有的询问再一并输出。在这个过程中,Tarjan算法会改变处理询问的次序,而这也就是Tarjan算法的精髓所在。

另外,Tarjan算法是基于时空复杂度优越的并查集的。所以说如果并查集都不了解的话,不妨先学学再来。好,现在正式开始Tarjan算法的教学。

Tarjan算法处理某一个节点X的过程分为这么几步:

1、建立只有一个X节点的集合。也就是在并查集里,root[X] = X。

2、处理所有关于X的询问,对于(X, Y),如果Y已经处理过,那么LCA(X, Y) = find(Y),也就是Y在并查集里的根节点。如果Y没有处理过,忽略这个询问。

注意:应该使得(X, Y)在X和Y处都能够访问到。

3、将X设置为已处理。

4、递归这个过程处理X的孩子。

5、将root[X]设为father[X],也就是X的父亲。

以下是本人对于这个算法的理解:

LCA(X, Y) = L的含义就是X和Y分别在L的两棵子树里。如果X和Y在L的同一棵子树里面,那么在第五步这棵子树还没有链接到父亲以前,X和Y就应该已经被检索到了,他们的最近公共祖先自然不会被设置成L;如果X或者Y有一个不属于L,那么第二步的时候不可能检索到这一个,只有L进入更高级的单位的时候,Y才会被检索到。所以说这个算法的正确性是可以相信的。

这样做之所以能够降低复杂度,就是因为这个算法实时处理了能够处理的询问。把一个询问同时挂靠在两个点上的时候,就能够保证迟早能在检索一个元素的时候另一个已经被检索到了。所以说所有的询问都能“顺便被处理”,我们要做的只是一次DFS而已。

现在还有几个小问题:

一、形如(X, X)的询问怎么办?很好办,因为这根本就不用处理。但是一定要把它剔除出去。

二、怎样处理某一个节点的询问?绝对不能每次都扫描,那就成了O(NK)了。实际上,用一个邻接链表把询问“挂”在节点上是一个不错的选择。

有了LCA Tarjan,这个题就小意思了。设LCA(X, Y) = L,dist(X)表示X到根节点的距离(这可以由DFS得到),那么X到Y的路径长度就是dist(X) + dist(Y) - 2 * dist(L)。

---------------------------------------(以上为转载)----------------------------------------------

思路:这题前几日做过了,但是用的搜索,所以WA了两次,T了几发,然后就暂时不做,停下学习图论,现在学到有向图的Tarjan算法,然后回来重新学了LCA Tarjan算法。

这个算法,上面有很好的解释了,就是边访问,然后边处理访问过的询问……我用的是和前几题一样的邻接表,如果用vector的邻接矩阵的话,效率就慢了好多了……这个算法其实也不难理解,就是用并查集合并,并且找到祖先,确定祖先,用dfs思想递归处理全部的数据。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define M 1000002
#define INF 1000001
using namespace std;
typedef long long ll;
int n,m,t,t1,dist[M],head[M],head1[M],vis[M],father[M],abc[M];
struct edge
{
    int v,l,next;
} e[M];
struct node
{
    int i,v,next;
}no[M];
void add(int u,int v,int l)
{
    e[t].v=v; e[t].l=l;       //邻接表
    e[t].next=head[u]; head[u]=t++;
}
void add1(int u,int v,int i)
{
    no[t1].i=i; no[t1].v=v;   //邻接表
    no[t1].next=head1[u]; head1[u]=t1++;
}
int find(int x)
{
    return father[x]==x?x:father[x]=find(father[x]); //并查集
}
void LCATarjan(int u,int l)
{
    dist[u]=l; father[u]=u; vis[u]=1;
    for(int i=head[u]; i!=-1; i=e[i].next)
    {
        if(!vis[e[i].v])
        {
            dfs(e[i].v,l+e[i].l);
            father[e[i].v]=u;   //为了代码比较少,所以我没有用加权法确定祖先,如果用加权法合并的话,时间应该会更快一些
        }
    }
    for(int i=head1[u]; i!=-1; i=no[i].next)
    {
        if(vis[no[i].v])
            abc[no[i].i]=dist[u]+dist[no[i].v]-2*dist[find(no[i].v)];
    }
}
int main()
{
    int u,v,l,i,k;
    scanf("%d%d",&n,&m);
    mem(head,-1); mem(head1,-1);
    for(i=0; i<m; i++)
    {
        scanf("%d%d%d %*c",&u,&v,&l);
        add(u,v,l); add(v,u,l);
    }
    scanf("%d",&k);
    for(i=0;i<k;i++)
    {
        scanf("%d%d",&u,&v);
        add1(u,v,i); add1(v,u,i);
    }
    LCATarjan(1,0);
    for(i=0;i<k;i++)
        printf("%d\n",abc[i]);
    return 0;
}


CUGB图论专场:G - Distance Queries(LCA Tarjan算法)

上一篇:图解Git [转载]


下一篇:ssh 组合键注解方式