HDU 2586 How far away ？

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

给出一颗无向有边权树, 询问若干个(u,v)对的距离。

题目链接 HDU 2586

题目大意

给你一棵有边权树，求两点之间的最短距离。
两点的最短边其实就是两点之间过LCA的那条边，因此两点间的距离就是这条边的
长度。

photo

如图，求K与F的距离。
我们用dist[x]保存 x到根节点A的距离。
则K与F的距离等于dist[K]+dist[F]-2*dist[B] (B为K与F的LCA).

LCA模板详解链接

LCA-RMQ-ST算法

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define maxn 40005
struct node
{
        int x,l;
};
vector<node> V[maxn];
int E[maxn * 2], D[maxn * 2], first[maxn];
int vis[maxn], dist[maxn], n, m, top = 1, root[maxn], st;
int dp[30][maxn * 2];
void init()
{
        top = 1;
        memset(root, 0, sizeof(root));
        memset(vis, 0, sizeof(vis));
        scanf("%d %d", &n,&m);
        for (int i = 1; i <= n; i++)
        {
                V[i].clear();
        }
        int a, b,c;
        node tmp;
        for (int i = 0; i < n - 1; i++)
        {
                scanf("%d%d%d", &a, &b,&c);
                tmp.x = b;
                tmp.l=c;
                V[a].push_back(tmp);
                tmp.x = a;
                V[b].push_back(tmp);
                root[b] = 1;
        }
        for (int i = 1; i <= n; i++)
                if (root[i] == 0)
                {
                        st = i;
                        break;
                }
        dist[st]=0;//dist[] 初始化
}
void dfs(int u, int dep)
{
        vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++;
        for (int i = 0; i < V[u].size(); i++)
                if (!vis[V[u][i].x])
                {
                        int v = V[u][i].x;
                        dist[v]=dist[u]+V[u][i].l; //dist[] 更新
                        dfs(v, dep + 1);
                        E[top] = u, D[top++] = dep;
                }
}
void ST(int num)
{
        for (int i = 1; i <= num; i++)
        {
                dp[0][i] = i;
        }
        for (int i = 1; i <= log2(num); i++)
                for (int j = 1; j <= num; j++)
                        if (j + (1 << i) - 1 <= num)
                        {
                                int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)];
                                if (D[a] < D[b])
                                {
                                        dp[i][j] = a;
                                }
                                else
                                {
                                        dp[i][j] = b;
                                }
                        }
}
int RMQ(int x, int y)
{
        int k = (int) log2(y - x + 1.0);
        int a = dp[k][x], b = dp[k][y - (1 << k) + 1];
        if (D[a] < D[b])
        {
                return a;
        }
        return b;
}
int main ()
{
        int T;
        scanf("%d", &T);
        while (T--)
        {
                init();
                dfs(st, 0);
                ST(top);
                int x, y;
                while(m--)
                {
                        scanf("%d%d", &x, &y);
                        int a = first[x], b = first[y];
                        if (a > b)
                        {
                                swap(a, b);
                        }
                        int pos = RMQ(a, b);
                        printf("%d\n",dist[x]+dist[y]-2*dist[E[pos]]);
                }
        }
        return 0;
}

Tarjan离线算法

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define maxn 40005
int pre[maxn], point[maxn], point2[maxn], dist[maxn];
bool vis[maxn];
struct Edge
{
        int v;
        int l;
        int next;
} edge[maxn * 2];
struct Query
{
        int v;
        int w;
        int u;
        int next;
} query[maxn];
int top, top2;
int init()
{
        memset(vis, 0, sizeof(vis));
        memset(point, -1, sizeof(point));
        memset(point2, -1, sizeof(point2));
        top = 0;
        top2 = 0;
}
int add_edge(int u, int v, int l)
{
        edge[top].v = v;
        edge[top].l = l;
        edge[top].next = point[u]; 
        point[u] = top++; 
}
int findset(int x) 
{
        if (x != pre[x])
        {
                pre[x] = findset(pre[x]); 
        }
        return pre[x];
}
int add_query(int u, int v)
{
        query[top2].v = v;
        query[top2].u = u;
        query[top2].w = -1;
        query[top2].next = point2[u]; 
        point2[u] = top2++; 
        query[top2].v = u;
        query[top2].u = v;
        query[top2].w = -1;
        query[top2].next = point2[v]; 
        point2[v] = top2++; 
}
int lca(int u, int f)
{
        pre[u] = u; 
        for (int i = point[u]; i != -1; i = edge[i].next)
        {
                if (edge[i].v == f)
                {
                        continue;
                }
                dist[edge[i].v] = dist[u] + edge[i].l;//dist[] 更新
                lca(edge[i].v, u);
                pre[edge[i].v] = u; 
        }
        vis[u] = 1; 
        for (int i = point2[u]; i != -1; i = query[i].next)
        {
                if (vis[query[i].v] == 1)
                {
                        query[i].w = findset(query[i].v);
                }
        }
        return 0;
}
int main()
{
        int root[maxn];
        int T;
        scanf("%d", &T);
        for (int ii = 0; ii < T; ii++)
        {
                init();
                int tot, r = -1, a, b, c, m;
                scanf("%d %d", &tot, &m);
                for (int i = 1; i <= tot; i++)
                {
                        root[i] = i;
                }
                for (int i = 0; i < tot - 1; i++)
                {
                        scanf("%d%d%d", &a, &b, &c);
                        add_edge(a, b, c);
                        add_edge(b, a, c);
                        root[b] = a;
                }
                for (int i = 1; i <= tot; i++)
                        if (root[i] == i)
                        {
                                r = i;  
                        }
                memset(dist, 0, sizeof(dist)); //dist[] 初始化
                while (m--)
                {
                        scanf("%d%d", &a, &b);
                        add_query(a, b);
                }
                lca(r, r);
                for (int i = 0; i < top2; i++)
                {
                        if (query[i].w != -1)
                        {
                                printf("%d\n", dist[query[i].v] + dist[query[i].u] - 2 * dist[query[i].w]);
                        }
                }
        }
        return 0;
}

倍增算法（在线）

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#pragma comment(linker, "/STACK:10240000000,10240000000")//扩栈，要用c++交，用g++交并没有什么卵用。。。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int N = 40015;
int n , m , pre[N] , rt[N], mcnt;
bool vis[N];
struct edge
{
        int x ,val, next;
} e[N << 1];
int dep[N] , f[17][N] , dist[N],Lev , s[N];
void dfs(int x , int fa)
{
        dep[x] = dep[fa] + 1;
        f[0][x] = fa , s[x] = 1;
        for (int i = pre[x] ; i!=-1 ; i = e[i].next)
        {
                int y = e[i].x;
                if (y != fa)
                {
                        dist[y]=dist[x]+e[i].val;
                        dfs(y , x);
                        s[x] += s[y];
                }
        }
}
void bfs(int rt)
{
        queue<int> q;
        q.push(rt);
        f[0][rt] = 0, dep[rt] = 1, vis[rt] = 1;
        while (!q.empty())
        {
                int fa = q.front();
                q.pop();
                for (int i = pre[fa] ; ~i ; i = e[i].next)
                {
                        int x = e[i].x;
                        if (!vis[x])
                        {
                                dep[x] = dep[fa] + 1;
                                f[0][x] = fa , vis[x] = 1;
                                q.push(x);
                        }
                }
        }
}
int LCA(int x , int y)
{
        if (dep[x] > dep[y])
        {
                swap(x , y);
        }
        for (int i = Lev ; i >= 0 ; -- i)
                if (dep[y] - dep[x] >> i & 1)
                {
                        y = f[i][y];
                }
        if (x == y)
        {
                return y;
        }
        for (int i = Lev ; i >= 0 ; -- i)
                if (f[i][x] != f[i][y])
                {
                        x = f[i][x] , y = f[i][y];
                }
        return f[0][x];
}
int get_kth_anc(int x , int k)
{
        for (int i = 0 ; i <= Lev ; ++ i)
                if (k >> i & 1)
                {
                        x = f[i][x];
                }
        return x;
}
void init()
{
        memset(pre , -1 , sizeof(pre));
        memset(rt, 0, sizeof(rt));
        memset(dist,0,sizeof(dist));
        mcnt = 0;
}
void addedge(int x, int y,int val)
{
        e[mcnt].x = y;
        e[mcnt].val=val;
        e[mcnt].next = pre[x];
        pre[x] = mcnt ++;
}
void work()
{
        int i , j , x , y , z, anc;
        init();
        scanf("%d%d", &n,&m);
        for (i = 1 ; i < n ; ++ i)
        {
                scanf("%d%d%d", &x, &y,&z);
                addedge(x, y,z);
                addedge(y,x,z);
                rt[y]  = x;
        }
        for (int i = 1; i <= n; i++)
        {
                if (rt[i] == 0)
                {
                        anc = i;
                        break;
                }
        }
        dfs(anc , 0);
        for (j = 1 ; 1 << j < n ; ++ j)
                for (i = 1 ; i <= n ; ++ i)
                {
                        f[j][i] = f[j - 1][f[j - 1][i]];
                }
        Lev = j - 1;
        while(m--)
        {
                scanf("%d%d", &x, &y);
                printf("%d\n", dist[x]+dist[y]-2*dist[LCA(x , y)]);
        }
}
int main()
{
        int t;
        scanf("%d", &t);
        while (t--)
        {
                work();
        }
        return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！