LG1967【NOIp2013】货车运输 < MST+LCA >

Posted on Symbols count in article: 992 Reading time ≈ 4 mins.

Problem

货车运输

题目描述

AA 国有 nn 座城市，编号从 11 到 nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 qq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：
输入文件名为 truck.intruck.in。
输入文件第一行有两个用一个空格隔开的整数 nn, mm，表示 AA 国有 nn 座城市和 mm 条道路。 接下来 mm 行每行 33 个整数 xx、 yy、 zz，每两个整数之间用一个空格隔开，表示从 xx 号城市到 yy 号城市有一条限重为 zz 的道路。注意： xx 不等于 yy，两座城市之间可能有多条道路 。
接下来一行有一个整数 qq，表示有 qq 辆货车需要运货。
接下来 qq 行，每行两个整数 xx、yy，之间用一个空格隔开，表示一辆货车需要从 xx 城市运输货物到 yy 城市，注意： xx 不等于 yy 。
输出格式：
输出文件名为 truck.outtruck.out。
输出共有 qq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出−1-1。

输入输出样例

输入样例#1\#1：

1
2
3
4
5
6
7
8
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出样例#1\#1：

1
2
3
3
-1
3

说明

对于 30%30\%的数据，0<n<10000 < n < 1000，0<m<100000 < m < 10000，0<q<10000 < q< 1000；
对于 60%60\%的数据，0<n<10000 < n < 1000，0<m<500000 < m < 50000，0<q<10000 < q< 1000；
对于 100%100\%的数据，0<n<100000 < n < 10000，0<m<500000 < m < 50000，0<q<300000 < q< 30000，0≤z≤1000000 \le z \le 100000。

标签：MST LCA

Solution

LCALCA经典例题。
为了使得货车走过的路径上最小权最大，又要使其能到任意两点，那么该图可以缩减成一棵树，为了保证最优解，该树采用原图的最大生成树。
对于一次询问，在最大生成树上跑两点的LCALCA，倍增统计路径最小值即可。
不错的板题

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX_N 10000
#define MAX_M 50000
#define INF 2147483647
using namespace std;
int n, m, q, cnt;
int first[MAX_N+5], d[MAX_N+5], p[MAX_N+5][15], f[MAX_N+5][15];
int father[MAX_N+5];
bool vis[MAX_N+5];
struct Edge {
    int from, to, c, next;
};
Edge G[MAX_M], edge[MAX_M+5];
inline int read() {
    int ret = 0;    char ch = getchar();
    while (ch < '0' || ch > '9')    ch = getchar();
    while (ch >= '0' && ch <= '9')    ret = ret*10+ch-'0', ch = getchar();
    return ret;
}
bool cmp (const Edge &a, const Edge &b) {
    return a.c > b.c;
}
void Add(int u, int v, int x) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].c = x;
    edge[cnt].next = first[u];
    first[u] = cnt;
}
int get_father(int cur) {
    if (father[cur] != cur)    father[cur] = get_father(father[cur]);
    return father[cur];
}
void Kruskal() {
    sort(G, G+m, cmp);
    for (int i = 1; i <= n; i++)    father[i] = i;
    for (int i = 0; i < m; i++) {
        int u = get_father(G[i].from), v = get_father(G[i].to);
        if (u != v) {
            father[u] = v;
            Add(G[i].from, G[i].to, G[i].c);
            Add(G[i].to, G[i].from, G[i].c);
        }
    }
}
void DFS(int u) {
    vis[u] = true;
    for (int i = 1; (1<<i) <= d[u]; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
        f[u][i] = min(f[u][i-1], f[p[u][i-1]][i-1]);
    }
    for (int i = first[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) {
            d[v] = d[u]+1;
            p[v][0] = u;
            f[v][0] = edge[i].c;
            DFS(v);
        }
    }
}
int LCA(int a, int b) {
    int ret = INF, i, j;
    if (d[a] < d[b])    swap(a, b);
    for (i = 0; (1<<i) <= d[a]; i++) {}    i--;
    for (j = i; j >= 0; j--) {
        if (d[a]-(1<<j) >= d[b]) {
            ret = min(ret, f[a][j]);
            a = p[a][j];
        }
    }
    if (a == b)    return ret;
    for (j = i; j >= 0; j--) {
        if (p[a][j] != p[b][j]) {
            ret = min(ret, min(f[a][j], f[b][j]));
            a = p[a][j];
            b = p[b][j];
        }
    }
    return min(ret, min(f[a][0], f[b][0]));
}
int main() {
    memset(f, 127, sizeof(f)); 
    n = read(), m = read();
    for (int i = 0; i < m; i++) {
        G[i].from = read(), G[i].to = read(), G[i].c = read();
    }
    Kruskal();
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && father[i] == i) {
            DFS(i);
        }
    }
    q = read();
    for (int i = 0; i < q; i++) {
        int a, b;
        a = read(), b = read();
        if (get_father(a) != get_father(b)) {
            printf("-1\n");
        } else {
            printf("%d\n", LCA(a, b));
        }
    }
    return 0;
}