hdu 2874 Connections between cities (并查集+LCA)hash优化

Connections between cities (并查集+LCA)hash优化"/>

hdu 2874 Connections between cities (并查集+LCA)hash优化

问题描述：
Problem Description
After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.

Input
Input consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.

Output

        For each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.

Sample Input
5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

Sample Output
Not connected
6

Hint

Hint

Huge input, scanf recommended.

大致题意：
给出一片森林，每个边都有一个权值。求2个节点的最短距离。

思路分析：

并查集+LCA。
今天只学了一个LCA的离线算法。
这个题和DD讨论了好大会。
由于对hash还不大熟悉，所以看了很长时间才弄懂。
hash主要是用空间换时间。我把那几个数组的作用都打上注释了。方便理解~

LCA思想。

       0|1/   \2      3

比如说在这里，如果0为根的话，那么1是2和3的父亲结点，0是1的父亲结点，0和1都是2和3的公共祖先结点，但是1才是最近的公共祖先结点，或者说1是2和3的所有祖先结点中距离根结点最远的祖先结点。

在求解最近公共祖先为问题上，用到的是Tarjan的思想，从根结点开始形成一棵深搜树，非常好的处理技巧就是在回溯到结点u的时候，u的子树已经遍历，这时候才把u结点放入合并集合中，这样u结点和所有u的子树中的结点的最近公共祖先就是u了，u和还未遍历的所有u的兄弟结点及子树中的最近公共祖先就是u的父亲结点。以此类推。。这样我们在对树深度遍历的时候就很自然的将树中的结点分成若干的集合，两个集合中的所属不同集合的任意一对顶点的公共祖先都是相同的，也就是说这两个集合的最近公共最先只有一个。

下面贴代码。
hash自己在纸上模拟一下就明白了~
ac代码：

#include<stdio.h>
#include<string.h>
#define M 10007
#define N 2222212
#include<iostream>
using namespace std;
int pre[M],dis[M],vis[M],ans[N],parent[M];
//pre存的是父亲，dis存的是到u的距离。vis记录是否遍历过。ans存的是询问的答案。parent是祖先。
int s1[N],s2[N],t[N],d[N],p[N];   //哈希用到的数组。
int n,m,ne,cnt;int findd(int x)
{while(x!=pre[x])x=pre[x];return x;
}void add(int u,int v,int w,int h[])//这里是哈希表优化来的。   没用邻接表存储，用的hash
{t[ne]=v,d[ne]=w,p[ne]=h[u],h[u]=ne++;t[ne]=u,d[ne]=w,p[ne]=h[v],h[v]=ne++;
}
//t记录的是这条边的终点。d是这条边的花费。p是后继结点的下标。h记录的是下标。
void Tarjan(int u)  //LCA离线算法。
{//cout<<"u"<<u<<endl;parent[u]=cnt;   //虚拟结点。pre[u]=u;vis[u]=1;for(int i=s2[u];i;i=p[i]){int v=t[i];if(vis[v])   //如果被访问过。{if(parent[u]==parent[v])//在同一棵树下{int rt=findd(v);//最近公共祖先//cout<<"rt "<<rt<<endl;ans[d[i]]=dis[u]+dis[v]-2*dis[rt];}elseans[d[i]]=-1;}}for(int i=s1[u];i;i=p[i])//这里是回溯求父节点{//cout<<"yes"<<endl;int v=t[i];if(!vis[v]){dis[v]=dis[u]+d[i];Tarjan(v);pre[v]=u;}}
}int main()
{int n,m,q,i,j;while(scanf("%d%d%d",&n,&m,&q)!=EOF){for(i=1,ne=1;i<=n;i++)  //初始化。{s1[i]=s2[i]=vis[i]=ans[i]=parent[i]=pre[i]=0;}int u,v,w;for(i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w,s1);}for(i=1;i<=q;i++){scanf("%d%d",&u,&v);add(u,v,i,s2);}for(i=1,cnt=1;i<=n;i++,cnt++)if(!vis[i]){dis[i]=0;Tarjan(i);}for(i=1;i<=q;i++)if(ans[i]>=0)printf("%d\n",ans[i]);elseprintf("Not connected\n");}return 0;
}