HDU-2874: Connections between cities（LCA+并查集）

LCA

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

Huge input, scanf recommended.

题意：输入n,m,c，表示有n个城市（编号1到n），之间有m条路，c次询问。输入m行表示x城市到y城市之间的距离为z，c次询问x城市到y城市的距离是多少，若两个城市不连通则输出Not connected。

分析：由于n的范围是10000，c的范围是一百万，因此不能用dij在每次询问之后求最短路，会超时。
求两点之间的距离可以用LCA，但是这道题给出的是森林，而不是树，因此我们首先使用并查集处理，判断节点是否在同一棵树上，然后再将根节点与虚节点（0）连接起来，使之构成一棵树，再利用LCA求解。

• 代码：

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
const int maxn=10005;
using namespace std;
int n,m,c;
int father[maxn];
int dep[maxn],dis[maxn];
int fa[maxn][15];
struct node
{
    int en,val;
    node(int enn=0,int vall=0)
    {
        en=enn;
        val=vall;
    }
};
vector<node> V[maxn];
void clr()
{
    memset(dep,0,sizeof(dep));
    memset(dis,0,sizeof(dis));
    memset(fa,0,sizeof(fa));
    for(int i=0;i<maxn;i++)
        father[i]=i;
    for(int i=0;i<=n;i++)
        V[i].clear();
}
int findx(int x)//并查集
{
    if(x!=father[x])
        father[x]=findx(father[x]);
    return father[x];
}
void merge(int a,int b)//将father统一为树上最小一点
{
    int x=findx(a);
    int y=findx(b);
    if(x>y)
        father[x]=y;
    else
        father[y]=x;
}
void dfs(int u,int f,int d)
{
    fa[u][0]=f;
    for(int i=1;i<15;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    dep[u]=d;
    for(int i=0;i<V[u].size();i++)
    {
        node v=V[u][i];
        if(v.en==f) continue;
        dis[v.en]=dis[u]+v.val;
        dfs(v.en,u,d+1);
    }
}
int LCA(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    for(int i=0;i<15;i++)
        if((dep[v]-dep[u])>>i&1)
        v=fa[v][i];
    if(u==v)
        return u;
    for(int i=14;i>=0;i--)
    {
        if(fa[u][i]!=fa[v][i])
        {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
void solve()
{
    for(int i=1;i<=n;i++)//若为根节点，则连接到序号为0的虚根上
        if(father[i]==i)
    {
        V[i].push_back(node(0,0));
        V[0].push_back(node(i,0));
    }
    dfs(0,-1,1);//节点为0，父节点-1，深度为1
}
int main()
{
    int x,y,z;
    while(scanf("%d%d%d",&n,&m,&c)!=EOF)
    {
        clr();
        while(m--)
        {
            scanf("%d%d%d",&x,&y,&z);
            merge(x,y);
            V[x].push_back(node(y,z));
            V[y].push_back(node(x,z));
        }
        solve();
        while(c--)
        {
            scanf("%d%d",&x,&y);
            if(findx(x)!=findx(y))//不在同一棵树上
                printf("Not connected\n");
            else
                printf("%d\n",dis[x]+dis[y]-2*dis[LCA(x,y)]);
        }
    }
    return 0;
}