Distance Queries POJ - 1986 (tarjan离线LCA)

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. 

解题思路:

Tarjan离线算法,注意本结点的父节点要在tarjan函数递归完成后赋值

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <map>
using namespace std;
const int MAX_N = 80010;  //点和边是一样的
struct edgeVal {
	int to, len;
};

//得出每个结点到根结点的距离
int N, M, Q;  //输入点,边,查询数
int nVis[MAX_N];
int nFather[MAX_N]; //用来表示父亲结点
int cDis[MAX_N];  //距离根节点的距离
int resDis;
vector<edgeVal> querys[MAX_N], nEdges[MAX_N];  //将查询结果保存
int sAns[MAX_N];  //查询结果

//寻找公共祖先
int sfindFa(int sroot) {
	if (nFather[sroot] != sroot) {
		return sfindFa(nFather[sroot]);  //向下查找
	}
	return sroot;  //返回根节点
}

void wAdd_Edge(int a, int b,int l) {
	edgeVal te;
	te.to = b;
	te.len = l;
	nEdges[a].push_back(te);   //有向边
	te.to = a;
	nEdges[b].push_back(te);
}

//LCA算法
void sTarjan(int sroot,int curLen) {
	//向下查找
	nVis[sroot] = true;
	cDis[sroot] = curLen;
	
	for (int j = 0; j < querys[sroot].size(); ++j) {
		if (nVis[querys[sroot][j].to]) {
			int sancestor = sfindFa(querys[sroot][j].to);
			sAns[querys[sroot][j].len] = cDis[querys[sroot][j].to] + cDis[sroot] - 2 * cDis[sancestor]; //要剪去它们公共长度的高度
		}
	}
	
	for (int i = 0; i < nEdges[sroot].size(); ++i) {
		//没有被访问过的话
		if (!nVis[nEdges[sroot][i].to]) {
			sTarjan(nEdges[sroot][i].to,curLen + nEdges[sroot][i].len);
			nFather[nEdges[sroot][i].to] = sroot;  //注意父节点要在这个位置保存,否则会出错
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);  
	int a, b, l;
	char c;
	for (int i = 0; i < M; ++i) {
		scanf("%d %d %d %c", &a, &b, &l, &c);
		wAdd_Edge(a, b, l);
	}
	scanf("%d", &Q);  
	int la, lb;
	for(int i = 0; i < Q;++i){
		scanf("%d %d", &la, &lb);  
		edgeVal tempe;
		tempe.to = lb;
		tempe.len = i;
		querys[la].push_back(tempe);  //将查询结果保存
		tempe.to = la;
		querys[lb].push_back(tempe);
		
	}
	memset(nVis, false, sizeof(nVis));
	for (int i = 1; i <= N+10; ++i) {
		nFather[i] = i;
	}
	sTarjan(1, 0);   //开始tarjan查询

	//最后输出结果
	for (int i = 0; i < Q; ++i) {
		printf("%d\n",sAns[i]);
	}

	system("PAUSE");
	return 0;
}