Codevs 3287 货车运输

题目描述 Description

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

输入描述 Input Description

第一行有两个用一个空格隔开的整数 n, m，表示 A 国有 n 座城市和 m 条道路。

接下来 m 行每行 3 个整数 x, y, z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x, y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。

输出描述 Output Description

输出共有q行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

样例输入 Sample Input

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 Sample Output

3
-1
3

数据范围及提示 Data Size & Hint

对于 30%的数据，0<n<1000,0<m<10000,0<q<1000；

对于 60%的数据，0<n<1000,0<m<50000,0<q<1000；

对于 100%的数据，0<n<10000,0<m<50000,0<q<30000，0≤z≤100000。

题解

• 最小生成树
• LCA

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1000000007
using namespace std;
struct et
{
int l, s, t;
};
bool operator < (const et &a, const et &b)
{
return a.l > b.l;
}
struct pt
{
int a, b;
pt(const int &x, const int &y)
{
a = x;
b = y;
}
pt()
{
a = 0;
b = 0;
}
};
int f[10010], m, n, z;
pt fa[10010];
et edge[50010];
vector<pt> c[10010], son[10010];
int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}
int depth[10010];
bool vis[10010];
deque<int> q;
int bfs(int s)
{
vis[s] = true;
depth[s] = 1;
q.push_back(s);
int now;
while (!q.empty())
{
now = q.front();
q.pop_front();
for (vector<pt>::iterator i = c[now].begin(); i != c[now].end(); ++i)
{
if (!vis[i -> a])
{
q.push_back(i -> a);
depth[i -> a] = depth[now] + 1;
vis[i -> a] = true;
fa[i -> a].a = now;
fa[i -> a].b = i -> b;
son[i -> a].push_back(*i);
}
}
}
}int query(int s, int t)
{
int x = s, y = t, ret = INF;
while (depth[x] < depth[y])
{
ret = min(ret, fa[y].b);
y = fa[y].a;
}
while (depth[x] > depth[y])
{
ret = min(ret, fa[x].b);
x = fa[x].a;
}
while (x != y)
{
ret = min(ret, fa[x].b);
x = fa[x].a;
ret = min(ret, fa[y].b);
y = fa[y].a;
}
return ret;
}int main ()
{
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin >> n >> m;
for (int i = 0 ; i < m; ++i)
cin >> edge[i].s >> edge[i].t >> edge[i].l;
sort(edge, edge + m);
for (int i = 1; i <= n; ++i)
f[i] = i;
int p = 0;
for (int i = 1; i < n; ++i)
{
while (find(edge[p].s) == find(edge[p].t) && p < m)
++p;
if (p >= m)
break;
f[find(edge[p].s)] = find(edge[p].t);
c[edge[p].s].push_back(pt(edge[p].t, edge[p].l));
c[edge[p].t].push_back(pt(edge[p].s, edge[p].l));
++p;
}
bfs(1);
int qq;
cin >> qq;
int a, b;
for (int i = 0; i < qq; i++)
{
cin >> a >> b;
if (find(a) != find(b))
cout << -1 << endl;
else
cout << query(a, b) << endl;
}
}

运行结果（有点慢 LCA 毕竟用的是朴素）

测试通过 Accepted

总耗时: 1033 ms

0 / 0 数据通过测试.

运行结果

测试点#truck1.in 结果:AC 内存使用量: 872kB 时间使用量: 1ms

测试点#truck10.in 结果:AC 内存使用量: 1384kB 时间使用量: 24ms

测试点#truck11.in 结果:AC 内存使用量: 1512kB 时间使用量: 26ms

测试点#truck12.in 结果:AC 内存使用量: 1512kB 时间使用量: 23ms

测试点#truck13.in 结果:AC 内存使用量: 2280kB 时间使用量: 115ms

测试点#truck14.in 结果:AC 内存使用量: 2152kB 时间使用量: 119ms

测试点#truck15.in 结果:AC 内存使用量: 2156kB 时间使用量: 102ms

测试点#truck16.in 结果:AC 内存使用量: 2028kB 时间使用量: 97ms

测试点#truck17.in 结果:AC 内存使用量: 2280kB 时间使用量: 113ms

测试点#truck18.in 结果:AC 内存使用量: 2028kB 时间使用量: 104ms

测试点#truck19.in 结果:AC 内存使用量: 2024kB 时间使用量: 108ms

测试点#truck2.in 结果:AC 内存使用量: 748kB 时间使用量: 1ms

测试点#truck20.in 结果:AC 内存使用量: 2156kB 时间使用量: 105ms

测试点#truck3.in 结果:AC 内存使用量: 1000kB 时间使用量: 4ms

测试点#truck4.in 结果:AC 内存使用量: 1004kB 时间使用量: 5ms

测试点#truck5.in 结果:AC 内存使用量: 1004kB 时间使用量: 8ms

测试点#truck6.in 结果:AC 内存使用量: 872kB 时间使用量: 4ms

测试点#truck7.in 结果:AC 内存使用量: 1512kB 时间使用量: 28ms

测试点#truck8.in 结果:AC 内存使用量: 1388kB 时间使用量: 24ms

测试点#truck9.in 结果:AC 内存使用量: 1388kB 时间使用量: 22ms