解題區/解題區 - UVa

UVa 12655 - Trucks

contents

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

Problem

給一張 N 個點的圖，問任意兩點之間的最大化最小邊。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4 5 4
1 2 9
1 3 0
2 3 8
2 4 7
3 4 4
1 4
2 1
3 1
4 3
4 5 2
1 2 30
2 3 20
3 4 10
4 1 40
2 4 50
1 3
1 2

Sample Output

1
2
3
4
5
6
7
9
8
7
20
40

Solution

先將圖縮成最大生成樹，然後使用 tarjan 作離線的 LCA 詢問。

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

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

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

這題跟 UVa 12176 - Bring Your Own Horse 相當相似。

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
#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];
int visited[32767];
vector<E> tree[32767];
int parent[32767], weight[32767];
int findp(int x) {
    return parent[x] == x ? x : (parent[x] = findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
int kruscal(int n, int m) {
    int sum = 0;
    
    sort(D, D+m);
    for(int i = 0; i <= n; i++) {
        parent[i] = i, weight[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));
        }
    }
    return sum;
}
int dp[32767][20], dpw[32767][20];
int treeLevel[32767], treePath[32767];
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] = min(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);
    }
}
// LCA
vector< pair<int, int> > Q[32767];// query pair, input index - node
int LCA[131072];//input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i].y;
    	if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int query(int x, int y, int lca) {
    int hx = treeLevel[x], hy = treeLevel[y], hlca = treeLevel[lca];
    int ret = 0x3f3f3f3f;
    for(int i = 16; i >= 0; i--) {
        if (hx-hlca >= (1<<i)) {
            ret = min(ret, dp[x][i]);
            x = dpw[x][i];
            hx -= (1<<i);
        }
        if (hy - hlca >= (1<<i)) {
            ret = min(ret, dp[y][i]);
            y = dpw[y][i];
            hy -= (1<<i);
        }
    }
    return ret;
}
int main() {
    //	freopen("in.txt", "r+t", stdin);
    //	freopen("out.txt", "w+t", stdout);
    int n, m, q, x, y;
    while(scanf("%d %d %d", &n, &m, &q) == 3) {
        
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);
        }
        
        kruscal(n, m);
        memset(dp, 0, sizeof(dp));
        memset(dpw, 0, sizeof(dpw));
        dfs(1, -1, 1);
        
        for (int i = 1; i <= n; i++)
            visited[i] = 0, Q[i].clear();
        
        vector< pair<int, int> > ask;
        for (int i = 0; i < q; i++) {
        	scanf("%d %d", &x, &y);
        	Q[x].push_back(make_pair(i, y));
        	Q[y].push_back(make_pair(i, x));
            ask.push_back(make_pair(x, y));
        }
        tarjan(1, -1);
        
        for (int i = 0; i < q; i++) {
//            printf("%d %d %d\n", ask[i].first, ask[i].second, LCA[i]);
            printf("%d\n", query(ask[i].first, ask[i].second, LCA[i]));
        }
    }
    return 0;
}
/*
 */