HDU 2874 Connections between cities(倍增)

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

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

题意：

给你一个森林，求两个点之间的距离是多少，如果这两个点没有在同一棵树上则输出"Not connected";
输入表示的意思：
    第一行输入三个n,m,k;表示这个森林有n个点，接下来m行表示各个节点的关系；k表示要查询的k组数据；

解题思路：

如果两个点在同一棵树上，要求他们间的距离就只需要找出他们的最近公共祖先，dis=dis[x]+dis[v]-2*dis[lca(u,v)]就可以了
主要是当u和v不在同意棵树上的时候；
    我们可以用一个数组来存每个节点的根节点，如果它们的根节点相同则他们在同一棵数上，如果不同则不在同一棵树上；

完整代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 10010
int dep[N];///深度
int p[N][20];///p[i][j]表示i的2^j倍祖先
int dis[N];///距离
int root[N];///存根节点
int n;
struct node
{
    int w,l;
    node(int ww=0,int ll=0)
    {
        w=ww;
        l=ll;
    }
};
vector<node>g[N];
void dfs(int u,int f,int d,int id)///id表示这棵树的根节点
{
    dep[u]=d;
    p[u][0]=f;
    root[u]=id;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i].w;
        if(v==f)
            continue;
        dis[v]=dis[u]+g[u][i].l;
        dfs(v,u,d+1,id);
    }
}
void init()
{
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(p[i][j]!=-1)
            p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    int i;
    for(i=0;(1<<i)<=dep[v];i++);
    for(int j=i-1;j>=0;j--)
        if(dep[v]-(1<<j)>=dep[u])
            v=p[v][j];
    if(u==v)
        return u;
    for(int j=i-1;j>=0;j--)
    {
        if(p[v][j]!=-1&&p[u][j]!=p[v][j])
        {
            u=p[u][j];
            v=p[v][j];
        }
    }
    return p[u][0];
}
int main()
{
    int m,k;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        int a,b,c;
        memset(dis,0,sizeof(dis));
        memset(root,0,sizeof(root));
        for(int i=0;i<=n;i++)
            g[i].clear();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            g[a].push_back(node(b,c));
            g[b].push_back(node(a,c));
        }
        for(int i=1;i<=n;i++)
            if(root[i]==0)
                dfs(i,0,0,i);
        init();
        int x,y;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d",&x,&y);
            if(root[x]!=root[y])
                printf("Not connected\n");
            else
                printf("%d\n",dis[x]+dis[y]-2*dis[lca(x,y)]);
        }//
    }
    return 0;
}