算法竞赛备考冲刺必刷题（C++） | 洛谷 P1967 货车运输 - 实践

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：[P1967 NOIP 2013 提高组] 货车运输 - 洛谷

【题目描述】

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

【输入】

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

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

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

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x\ne y$。

【输出】

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

【输入样例】

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

【输出样例】

3
-1
3

【算法标签】

《洛谷 P1967 货车运输》 #图论# #贪心# #倍增# #并查集# #Kruskal重构树# #生成树# #最近公共祖先LCA# #NOIP提高组# #2013#

【代码详解】

#include <bits/stdc++.h>using namespace std;const int N = 10005;        // 最大节点数const int M = 80005;        // 最大边数// 边结构体struct Edge{int a, b, w = -1;       // 边的两个端点和权重，默认-1} e[M];int n, m, k;                // n:节点数, m:边数, k:查询数int p[N];                   // 并查集父节点数组int ans[30005];             // 存储每个查询的答案set<int> s[N];              // 每个连通分量中存储的查询ID集合set<int>::iterator it;      // 集合迭代器// 自定义比较函数：按权重降序排序bool cmp(Edge x, Edge y){return x.w > y.w;}// 并查集查找操作（带路径压缩）int find(int x){if (p[x] != x){p[x] = find(p[x]);}return p[x];}int main(){// 输入节点数和边数cin >> n >> m;// 输入所有边的信息for (int i = 1; i <= m; i++){int a, b, w;cin >> a >> b >> w;e[i] = {a, b, w};}// 将边按权重从大到小排序sort(e + 1, e + m + 1, cmp);// 初始化并查集for (int i = 1; i <= n; i++){p[i] = i;}// 输入查询数量cin >> k;int len = 0;  // 查询ID计数器// 处理每个查询for (int i = 1; i <= k; i++){len++;int a, b;cin >> a >> b;// 将查询ID添加到两个端点对应的集合中s[a].insert(len);s[b].insert(len);ans[len] = -1;  // 初始化答案为-1（表示尚未连通）}// 按权重从大到小处理边（类似Kruskal算法）for (int i = 1; i <= m; i++){int a = find(e[i].a);  // 查找起点所在连通分量的根int b = find(e[i].b);  // 查找终点所在连通分量的根int w = e[i].w;        // 当前边的权重// 如果两个端点不在同一个连通分量中if (a != b){// 启发式合并：总是将小集合合并到大集合if (s[a].size() < s[b].size()){swap(a, b);}// 遍历小集合中的所有查询IDfor (it = s[b].begin(); it != s[b].end(); it++){int id = *it;  // 查询ID// 如果大集合中也包含这个查询ID，说明两个端点现在连通了if (s[a].count(id)){ans[id] = w;      // 记录连通时的最小瓶颈权重s[a].erase(id);   // 从集合中移除已解决的查询}else{s[a].insert(id);  // 否则将查询ID加入大集合}}// 合并两个连通分量p[b] = a;}}// 输出所有查询的答案for (int i = 1; i <= k; i++){cout << ans[i] << endl;}return 0;}

【运行结果】

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