POJ 1986 Distance Queries

发表于   |   分类于   |     |   阅读次数

题目描述

Description

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.

题目链接

http://poj.org/problem?id=1986

解题思路

LCA的模板题，我分别用了Tarjan离线算法和在线算法。离线算法将所有的结果都保存起来了，所以耗时是在线算法的5倍。目前还没有完全理解LCA的相关算法，在这里只是Mark一下。

AC代码（离线算法）

21440K/1563MS/C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int maxn = 500005;
struct node
{
    int x;
    int d;   //存储距离
};
int dis[maxn], ans[maxn], vis[maxn], f[maxn];
vector<node> V[maxn], query[maxn];

int find(int x)
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}

void dfs(int u, int d)
{
    vis[u] = 1, f[u] = u, dis[u] = d;
    for (vector<node>::iterator it = query[u].begin(); it != query[u].end(); it++)
    {
        if (vis[(*it).x])
        {
            int v = (*it).x, w = (*it).d;
            ans[w] = dis[u] + dis[v] - 2 * dis[find(v)];
        }
    }
    for (vector<node>::iterator it = V[u].begin(); it != V[u].end(); it++)
    {
        if (!vis[(*it).x])
        {
            int v = (*it).x, w = (*it).d;
            dfs(v, d + w);
            f[v] = u;
        }
    }
}

int main ()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        memset(vis, false, sizeof(vis));
        int a, b;
        char str[5];
        node tmp;
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d%s", &a, &b, &tmp.d, str);
            tmp.x = b;
            V[a].push_back(tmp);
            tmp.x = a;
            V[b].push_back(tmp);
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d", &a, &b);
            tmp.d = i, tmp.x = b;
            query[a].push_back(tmp);
            tmp.x = a;
            query[b].push_back(tmp);
        }
        dfs(1, 0);
        for (int i = 0; i < m; i++)
        {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}

AC代码（在线算法）

6124K/250MS/C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>

const int MAXN = 50005;
struct Edge
{
    int v, next, w;
} edge[MAXN << 1];
int head[MAXN], cnt, fa[MAXN][20], dep[MAXN], dis[MAXN];
bool vis[MAXN];

void add_edge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void dfs(int now, int pre, int depth, int distance)
{
    fa[now][0] = pre;
    dep[now] = depth;
    dis[now] = distance;
    for (int i = 1; i < 20; i++)
        fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for (int i = head[now]; ~i; i = edge[i].next)
    {
        int next = edge[i].v, w = edge[i].w;
        if (next != pre) dfs(next, now, depth + w, distance + 1);
    }
}

int LCA(int x, int y)
{
    if(dis[x] > dis[y])
    {
        x ^= y;
        y ^= x;
        x ^= y;
    }
    for (int i = 0; i < 20; i++)
    {
        if(dis[y] - dis[x] & (1 << i))
        {
            y = fa[y][i];
        }
    }
    if(x == y) return x;
    for (int i = 19; i >= 0; i--)
    {
        if(fa[x][i] == fa[y][i]) continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    return fa[x][0];
}

int main()
{
    int n, m, q;
    int a, b, c;
    char str[5];
    while (~scanf("%d%d", &n, &m))
    {
        memset(head, -1, sizeof(head));
        cnt = 0;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d%s", &a, &b, &c, str);
            add_edge(a, b, c);
            add_edge(b, a, c);
        }
        dfs(1, 0, 1, 0);
        scanf("%d", &q);
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d", &a, &b);
            int dis = dep[a] + dep[b] - 2 * dep[LCA(a, b)];
            printf("%d\n", dis);
        }
    }
    return 0;
}