RenaMoe's Blog

念念不忘，必有回响

0%

题解 P1967 【货车运输】

发表于 更新于 分类于 ， Valine：

题面

思路

因为一些容量小的边不会被经过，考虑先建出最大生成树

题目转化成在树上求两点间路径最小权值

利用\(LCA\)求最短路径

另外搞一个倍增数组\(minn[x][i]\)，表示x到第\(2^i\)个祖先之间路径最小权值

转移：minn[x][i] = min(minn[x][i-1], minn[fa[x][i-1]][i-1]);

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

namespace BANANA {

template<typename T> inline void read(T &x) {
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

const int N = 1e4 + 5;
const int M = 5e4 + 5;
const int INF = 0x3f3f3f3f;

struct Edge_ {
    int x, y, w;
    bool operator <(const Edge_ &t) const {
        return w > t.w;// 从大到小排
    }
};

struct Edge {
    int nxt, to, w;
};

int n, m, q, cnt;
int head[N], col[N], fa[N][30], log[N], deep[N], minn[N][30];
bool vis[N];
Edge_ e_[M];
Edge e[M<<1];

inline void add(int u, int v, int w) {
    e[++cnt] = (Edge){head[u], v, w}, head[u] = cnt;
}

inline void swap(int &a, int &b) {
    int t = a;
    a = b, b = t;
}

// 并查集找father
int find(int x) {
    return col[x] == x ? x : col[x] = find(col[x]);
}

// 最大生成树
inline void Kruskal() {
    for (int i = 1; i <= n; ++i)
        col[i] = i;
    sort(e_+1, e_+m+1);
    for (int i = 1; i <= m; ++i)
        if (find(e_[i].x) != find(e_[i].y)) {
            col[find(e_[i].x)] = e_[i].y;
            add(e_[i].x, e_[i].y, e_[i].w), add(e_[i].y, e_[i].x, e_[i].w);
        }
}

// LCA预处理
void dfs(int x) {
    vis[x] = true;
    for (int i = 1; i <= log[deep[x]]; ++i)
        fa[x][i] = fa[fa[x][i-1]][i-1], minn[x][i] = min(minn[fa[x][i-1]][i-1], minn[x][i-1]);
    for (int i = head[x], y; i; i = e[i].nxt) {
        y = e[i].to;
        if (!vis[y]) {
            deep[y] = deep[x] + 1, fa[y][0] = x, minn[y][0] = e[i].w;
            dfs(y);
        }
    }
}

inline int LCA(int x, int y) {
    if (find(x) != find(y))
        return -1;
    int ans = INF;
    if (deep[x] < deep[y])
        swap(x, y);
    while (deep[x] > deep[y]) {
        ans = min(ans, minn[x][log[deep[x]-deep[y]]-1]);
        x = fa[x][log[deep[x]-deep[y]]-1];
    }
    if (x == y)
        return ans;
    for (int i = log[deep[x]]; ~i; --i)
        if (fa[x][i] != fa[y][i]) {
            ans = min(ans, min(minn[x][i], minn[y][i]));
            x = fa[x][i], y = fa[y][i];
        }
    ans = min(ans, min(minn[x][0], minn[y][0]));
    return ans;// 返回路径上最小值
}

inline void main() {
    read(n), read(m);
    for (int i = 1; i <= m; ++i)
        read(e_[i].x), read(e_[i].y), read(e_[i].w);

    Kruskal();
    // 递推log数组
    for (int i = 1; i <= n; ++i)
        log[i] = log[i-1] + ((1 << log[i-1]) == i);
    // 注意图不一定联通
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) {
            deep[i] = 1;
            fa[i][0] = i;
            minn[i][0] = INF;
            dfs(i);
        }

    read(q);
    int x, y;
    for (int i = 1; i <= q; ++i) {
        read(x), read(y);
        printf("%d\n", LCA(x, y));
    }
}
}

int main() {
    BANANA::main();
    return 0;
}