luogu - 1967

发表于 | 分类于 | 浏览
字数统计: 816 | 阅读时长 ≈ 4

luogu - 1967 货车运输

题目大意

有$n$个城市，$m$条双向道路，每一条道路有限重，现在有$q$辆货车分别向$u_{i}$城市送货到$v_{i}$城市，问你在不超过限重的情况下每辆车能运送货物的最大重量是多少

其中$1 \leq n < 10^{4}$，$1 \leq m < 5 \times 10^{4}$，$1 \leq q < 3 \times 10^{4}$

解题思路

首先很容易想到暴力的$Floyd$，转移方程也非常容易想到，即：

但是该算法时间复杂度$O(n^3)$，空间复杂度$O(n^2)$，显然不能满足要求，考虑优化。

模拟发现，如果$u_{i}$到$v_{i}$有多条道路，那么我们肯定会选择限重最大的那条路，并且不会去走边权小的道路，于是我们可以处理图中的最大生成树，这样就可以保证任意两个节点间的路径为最大。

其次，由于树上的任意两节点路径唯一，我们可以使用$LCA$来求得任意两节点间的路径。

总时间复杂度$O(mlog_{2}^{m}+(n + q)log_{2}^{n})$，空间复杂度$O(m+nlog_{2}^{n})$

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Edge {
    int u, v, w;
    Edge() { u = v = w = 0; }
    bool operator<(const Edge& obj)const {
        return w > obj.w;
    }
}edge[maxn];
vector<pair<int, int> > v[maxn];
int pre[maxn], fa[maxn][25], w[maxn][25];
bool vis[maxn];
int deep[maxn];
void dfs(int u) {
    vis[u] = true;
    int len = v[u].size();
    for(int i = 0; i < len; ++i) {
        if(vis[v[u][i].first]) continue;
        deep[v[u][i].first] = deep[u] + 1;
        fa[v[u][i].first][0] = u;
        w[v[u][i].first][0] = v[u][i].second;
        dfs(v[u][i].first);
    }
}
int find(int x) {
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
int lca(int u, int v) {
    if(find(u) != find(v)) return -1;
    int res = INF;
    if(deep[u] > deep[v]) swap(u, v);
    for(int i = 20; i >= 0; --i) {
        if(deep[fa[v][i]] >= deep[u]) {
            res = min(res, w[v][i]);
            v = fa[v][i];
        }
    }
    if(u == v) return res;
    for(int i = 20; i >= 0; --i) {
        if(fa[u][i] != fa[v][i]) {
            res = min(res, min(w[u][i], w[v][i]));
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    res = min(res, min(w[u][0], w[v][0]));
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) pre[i] = i;
    for(int i = 1; i <= m; ++i) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    sort(edge + 1, edge + m + 1);
    int cnt = 0;
    for(int i = 1; i <= m; ++i) {
        int fu = find(edge[i].u);
        int fv = find(edge[i].v);
        if(fu == fv) continue;
        pre[fv] = fu;
        v[edge[i].u].push_back(make_pair(edge[i].v, edge[i].w));
        v[edge[i].v].push_back(make_pair(edge[i].u, edge[i].w));
        ++cnt;
        if(cnt >= m - 1) break;
    }
    for(int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        deep[i] = 1;
        dfs(i);
        fa[i][0] = i;
        w[i][0] = INF;
    }
    for(int i = 1; i <= 20; ++i) {
        for(int j = 1; j <= n; ++j) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
            w[j][i] = min(w[j][i - 1], w[fa[j][i - 1]][i - 1]);
        }
    }
    int q;
    cin >> q;
    while(q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    return 0;
}