Description
Input
* 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
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
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; }