解題區/解題區 - UVa

UVa 12176 - Bring Your Own Horse

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Solution

Problem

One of the essential activities of a knight is to compete in tournaments. Frequently, groups of knights gather around the country to compare their skills. On such a typical contest day, everyone has five hours to do ten disciplines, such as sword fighting, bow and arrow, and various forms of horseback riding. Needless to say, you have to bring your own horse.

This is not as easy as it seems. It often takes a knight several days to go from the castle where he lives to the place where a tournament is held. But horses sometimes are very, very stubborn. After having covered a certain distance on a single day, they sometimes simply stop and refuse to go any further. Luckily, they start anew on the next day. To make sure that the horse does not refuse service before the scheduled day trip is completed, a knight wants to choose an itinerary on which the longest day trip is as short as possible. Hence, a trip that takes many days with short distances is preferable over a shorter route that has the risk of a refusing horse.

Write a program which answers queries from knights spread all over the country about the best way to go from their castles to a tournament site. Given a description of the relevant places (i.e. castles, locations of tournaments, and hostels for overnight stays), the program should tell them the largest distance they have to cover on a single day so that this distance is minimal among all possible itineraries.

The places are designated by consecutive integers from 1 to $N$, while a road is represented by three integers, namely its place of origin, its destination, and its length. Every road can be used in both directions, and there is at least one route (i.e. a sequence of roads) between any two places. The knights stick to the given roads while travelling and spend their nights only at one of the $N$ places.

Input

The first line contains the total number of test cases that follow.

Each test case begins with a line that first holds the number $N$ of places ( $1 \le N \le 3000$ ) followed by the number $R$ of roads ( $1 \le R \le 100000$ ). Then there are $R$ lines with three integers each ($a$ , $b$ , and $l$ ), each of which defines a road connecting the places $a$ and $b$ ( $1 \le a, b \le N$ ) with length $l$ ( $1 \le l \le 1000000$ ).

Thereafter, each test case continues with the number $Q$ of queries on a line by itself ( $1 \le Q \le 1000$ ). Each of the next $Q$ lines holds two integers $k$ and $t$ , indicating a query by a knight who lives at place $k$ and needs to go to a tournament at place $t$ ( $1 \le k, t \le N$ , $k \neq t$ ).

Output

For each test case output a line containing the word ``Case’’, a single space, and its serial number (starting with $1$ for the first test case). Then, print one line for each query in this test case, containing the smallest maximal day trip distance as described above. Print a blank line after each test case.

Sample Input

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
2
4 4
1 2 100
2 3 100
3 4 100
4 1 200
1
1 4
6 9
2 4 5
5 1 7
3 6 6
3 1 4
2 3 2
1 2 1
6 5 42
4 5 3
4 6 5
4
1 3
3 4
5 4
6 1
``` 
## Sample Output ##

Case 1
100

Case 2
2
5
3
5
```

Solution

題目描述：

騎士每天活動只會從該點移動到盡可能短的路徑到下一個點，求從起點到終點之間的最小的最長路為何。

題目解法：

由於詢問兩個點之間的路徑上的最小值最大邊，不外乎地可以先做一次最小成本樹，根據定義，拆分成 s - t 集合，最小成本樹的邊一定是 s - t 之間的最小邊。

接著詢問在樹上進行即可，因此每次詢問最慘會到 O(n)。

那我們稍微加速，採用 dp 的方式，將樹變成有根樹，記錄每一個節點向上攀升 1 個節點, 2 個節點, 4 個節點 …, 2^n 個節點的路徑上的最大最小值。

因此狀態會是 O(n log n), 建表也能在 O(n log n) 完成，接著調整兩個詢問節點的高度，先想辦法調整到兩個節點到水平高度，藉由之前的計算，高度不超過 n，因此理應可以在 O(log n) 時間內完成到調整到同一水平高度。

在同一水平下，還是需要知道 LCA 的所在高度，否則也可以水平線不斷地一步一步往上提，雖然最慘也許是 O(n) 但是經由之前的調整已經很加速很多。

本來應該套用 LCA Tarjan 的作法來加速，但是還沒有做到這樣的地步速度就很快。如果詢問次數再多一點就必須做到這一步。

有點懶惰 Orz。

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[100005];
vector<E> tree[3005];
int p[3005], rank[3005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m) {
    int sum = 0;
    
    sort(D, D+m);
    for(int i = 0; i <= n; i++) {
        p[i] = i, rank[i] = 1;
        tree[i].clear();
    }
    
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
        	sum += D[i].v;
        	tree[D[i].x].push_back(E(D[i].x, D[i].y, D[i].v));
        	tree[D[i].y].push_back(E(D[i].y, D[i].x, D[i].v));
//        	printf("mmm %d %d %d\n", D[i].x, D[i].y, D[i].v);
        }
    }
    return sum;
}
int dp[4096][20], dpw[4096][20];
int treeLevel[4096], treePath[4096];
void dfs(int u, int p, int level) {
    treeLevel[u] = level, treePath[level] = u;	
    for(int i = 1; (1<<i) < level; i++) {
        dp[u][i] = max(dp[u][i-1], dp[dpw[u][i-1]][i-1]);
        dpw[u][i] = treePath[level-(1<<i)];
    }
    for(int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if(v == p)	continue;		
        dp[v][0] = tree[u][i].v;
        dpw[v][0] = u;
        dfs(v, u, level + 1);
    }
}
int query(int x, int y) {
    int hx = treeLevel[x], hy = treeLevel[y];
    int ret = 0;
    while(x != y && hx != hy) {
        for(int i = 15; i >= 0; i--) {
            if(abs(hx-hy) >= (1<<i)) {
                if(hx > hy) {
                    ret = max(ret, dp[x][i]);
                    x = dpw[x][i];
                    hx -= (1<<i);
                } else {
                    ret = max(ret, dp[y][i]);
                    y = dpw[y][i];
                    hy -= (1<<i); 
                }
            }
        }
    }
    while(x != y) {
        ret = max(ret, dp[x][0]);
        x = dpw[x][0];
        hx -= (1<<0);
        ret = max(ret, dp[y][0]);
        y = dpw[y][0];
        hy -= (1<<0); 
    }
    return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m, q, x, y;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);        	
        }
        
        int mstcost = kruscal(n, m);
        memset(dp, 0, sizeof(dp));
        memset(dpw, 0, sizeof(dpw));
        dfs(1, -1, 1);
        
//		for(int i = 1; i <= n; i++, puts("")) {
//			printf("[%2d] :", i);
//			for(int j = 0; (1<<j) <= n; j++)
//				printf("%d %d, ", dp[i][j], dpw[i][j]);
//		}
        scanf("%d", &q);
        printf("Case %d\n", ++cases);
        while(q--) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query(x, y));
        }
        puts("");
    }
    return 0;
}
/*
5
10 45
1 2 15
1 3 11
1 4 48
1 5 24
1 6 45
1 7 18
1 8 12
1 9 40
1 10 11
2 3 4
2 4 9
2 5 44
2 6 23
2 7 39
2 8 48
2 9 48
2 10 22
3 4 42
3 5 37
3 6 10
3 7 18
3 8 29
3 9 8
3 10 47
4 5 7
4 6 17
4 7 25
4 8 23
4 9 32
4 10 27
5 6 26
5 7 21
5 8 38
5 9 40
5 10 39
6 7 35
6 8 11
6 9 39
6 10 1
7 8 15
7 9 10
7 10 47
8 9 28
8 10 11
9 10 1
30
1 6
5
10 45
1 2 9
1 3 12
1 4 21
1 5 4
1 6 32
1 7 20
1 8 14
1 9 28
1 10 16
2 3 12
2 4 23
2 5 27
2 6 34
2 7 43
2 8 2
2 9 33
2 10 35
3 4 41
3 5 26
3 6 16
3 7 39
3 8 2
3 9 49
3 10 44
4 5 24
4 6 2
4 7 17
4 8 26
4 9 20
4 10 2
5 6 23
5 7 5
5 8 41
5 9 12
5 10 15
6 7 48
6 8 45
6 9 13
6 10 28
7 8 25
7 9 12
7 10 37
8 9 4
8 10 5
9 10 41
30
5 4
1 7
8 4
*/