P1967-货车运输
题目:
题目描述:
A 国有 $n$ 座城市，编号从 $1 $ 到 $ n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式:
第一行有两个用一个空格隔开的整数 $ n,m$，表示 $A$ 国有 $ n$ 座城市和 $m$ 条道路。
接下来 $m$ 行每行三个整数 $x, y, z$，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 $z$ 的道路。
注意： $x \neq y$，两座城市之间可能有多条道路 。
接下来一行有一个整数 $q$，表示有 $q$ 辆货车需要运货。
接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x \neq y$
输出格式:
共有 $q$ 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 $-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:
思路:
最小生成树 + LCA
实现:
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
| #include <bits/stdc++.h>
#include "ybwhead/ios.h"
using namespace std;
int n, m;
pair<int, int> fa[10001][216];
int f[10001], ans[10001];
bool vis[10001];
int depp[10001];
vector<pair<int, int>> g[10001];
struct bian
{
int a, b, c;
} e[50001];
int find(int x)
{
if (x == f[x])
return x;
return f[x] = find(f[x]);
}
void dfs(int u, int dep)
{
vis[u] = 1;
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i].first;
if (vis[v])
continue;
fa[v][0].first = u;
depp[v] = dep + 1;
fa[v][0].second = g[u][i].second;
dfs(v, dep + 1);
}
return;
}
int LCA(int x, int y)
{
int ans = INT_MAX / 10;
if (depp[x] <= depp[y])
swap(x, y);
for (int i = 15; i >= 0; i--)
{
if (depp[fa[x][i].first] >= depp[y])
{
ans = min(fa[x][i].second, ans);
x = fa[x][i].first;
// cout<<fa[x][i].first<<endl;
}
}
if (x == y)
{
return ans;
}
for (int i = 15; i >= 0; i--)
{
if (fa[x][i].first != fa[y][i].first)
{
ans = min(ans, min(fa[x][i].second, fa[y][i].second));
x = fa[x][i].first;
y = fa[y][i].first;
}
}
ans = min(ans, min(fa[x][0].second, fa[y][0].second));
return ans;
}
int cmp(bian a, bian b)
{
return a.c > b.c;
}
int main()
{
yin >> n >> m;
for (int i = 1; i <= n; i++)
{
f[i] = i;
}
int x = 0;
for (int i = 1; i <= m; i++)
{
yin >> e[i].a >> e[i].b >> e[i].c;
}
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; i++)
{
int sa = find(e[i].a), sb = find(e[i].b);
if (sa != sb)
{
f[sa] = sb;
ans[++x] = i;
}
}
for (int i = 1; i <= x; i++)
{
g[e[ans[i]].a].push_back(make_pair(e[ans[i]].b, e[ans[i]].c));
g[e[ans[i]].b].push_back(make_pair(e[ans[i]].a, e[ans[i]].c));
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
depp[i] = 1;
dfs(i, 1);
fa[i][0].first = i;
fa[i][0].second = INT_MAX / 10;
// vis[i]=1;
}
}
for (int i = 0; i < 15; i++)
{
for (int u = 1; u <= n; u++)
{
fa[u][i + 1].first = fa[fa[u][i].first][i].first;
fa[u][i + 1].second = min(fa[u][i].second, fa[fa[u][i].first][i].second);
}
}
int q;
yin >> q;
for (int i = 1; i <= q; i++)
{
int x, y;
yin >> x >> y;
if (find(x) != find(y))
puts("-1");
else
yout << LCA(x, y) << endl;
}
return 0;
}
|