信奥赛C++提高组csp-s之倍增算法思想及应用案例（4）-编程实验室

信奥赛C++提高组csp-s之倍增算法思想及应用案例（4）

题目描述

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

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

输入格式

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3 -1 3

说明/提示

对于30 % 30\%30%的数据，1 ≤ n < 1000 1 \le n < 10001≤n<1000，1 ≤ m < 10 , 000 1 \le m < 10,0001≤m<10,000，1 ≤ q < 1000 1\le q< 10001≤q<1000；

对于60 % 60\%60%的数据，1 ≤ n < 1000 1 \le n < 10001≤n<1000，1 ≤ m < 5 × 10 4 1 \le m < 5\times 10^41≤m<5×104，1 ≤ q < 1000 1 \le q< 10001≤q<1000；

对于100 % 100\%100%的数据，1 ≤ n < 10 4 1 \le n < 10^41≤n<104，1 ≤ m < 5 × 10 4 1 \le m < 5\times 10^41≤m<5×104，$1 \le q< 3\times 10^4 $，0 ≤ z ≤ 10 5 0 \le z \le 10^50≤z≤105。

60分代码：最大生成树 + BFS查询

#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+10;// 最大节点数constintM=5e4+10;// 最大边数constintINF=0x3f3f3f3f;// 无穷大值intn,m,q;// 节点数，边数，查询数// 边结构体structnode{intx,y,z;// 边的两个端点和权重}a[M];structnode2{intto,w;};// 比较函数：按边权从大到小排序boolcmp(node a,node b){returna.z>b.z;}intfa[N];// 并查集数组// 并查集查找函数intfind(intx){if(fa[x]!=x)fa[x]=find(fa[x]);returnfa[x];}// 并查集合并函数voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx==rooty)return;fa[rooty]=rootx;}vector<node2>g[N];// 最大生成树的邻接表// BFS查找两点间路径上的最小边权intbfs(ints,inte){// 如果起点和终点不在同一个连通分量，直接返回-1if(find(s)!=find(e))return-1;vector<int>minw(n+1,-1);// 记录到达每个节点的路径上的最小边权queue<int>q;minw[s]=INF;// 起点到自己的最小边权设为无穷大q.push(s);while(!q.empty()){intu=q.front();q.pop();if(u==e)returnminw[u];// 到达终点，返回结果// 遍历当前节点的所有邻居for(autox:g[u]){intv=x.to;// 邻居节点intw=x.w;// 边权if(minw[v]==-1){// 如果邻居节点还未访问过minw[v]=min(minw[u],w);// 更新到v的最小边权q.push(v);}}}return-1;}intmain(){cin>>n>>m;// 输入所有边for(inti=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].z;}// 按边权从大到小排序sort(a+1,a+m+1,cmp);// 初始化并查集for(inti=1;i<=n;i++)fa[i]=i;// 构建最大生成树for(inti=1;i<=m;i++){intu=a[i].x;intv=a[i].y;intw=a[i].z;if(find(u)!=find(v)){// 如果两个节点不在同一个连通分量unionSet(u,v);// 合并g[u].push_back({v,w});// 在生成树中添加边g[v].push_back({u,w});}}// 处理查询cin>>q;while(q--){intx,y;cin>>x>>y;cout<<bfs(x,y)<<endl;// 输出两点间路径上的最小边权}return0;}

60分代码：功能分析

算法思路

最大生成树构建：
- 将边按权重从大到小排序
- 使用Kruskal算法构建最大生成树
- 这样保证任意两点间的路径上的最小边权是最大的
查询处理：
- 对于每个查询(x, y)，在最大生成树上进行BFS
- 在BFS过程中维护从起点到当前节点的路径上的最小边权
- 到达终点时，该值即为所求

关键特性

正确性保证：最大生成树保证了任意两点间路径的最小边权是原图中所有可能路径中最大的
效率优化：预处理构建生成树后，每个查询可以在O(n)时间内完成
连通性检查：使用并查集快速判断两点是否连通

时间复杂度

每个查询都进行一次完整的BFS，时间复杂度为O(n)
查询次数q最多可达 30,000，n最多可达 10,000
最坏情况复杂度：O(q × n) = 30,000 × 10,000 = 3×10⁸

满分代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+10;// 最大城市数constintM=5e4+10;// 最大道路数constintINF=0x3f3f3f3f;// 无穷大常量intn,m,q;// 存储原始道路信息structnode{intx,y,z;// x,y:城市编号, z:限重}a[M];// 存储生成树中的边structnode2{intto,w;// to:目标城市, w:边权(限重)};// 按限重从大到小排序，用于构建最大生成树boolcmp(node a,node b){returna.z>b.z;}// 并查集相关intfa[N];intfind(intx){if(fa[x]!=x)fa[x]=find(fa[x]);returnfa[x];}voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx==rooty)return;fa[rooty]=rootx;}// LCA相关常量与数组constintLOG=15;// 对数常数，2^15=32768 > 10000intd[N];// 节点深度intf[N][LOG];// f[i][j]:节点i的2^j级祖先intminw[N][LOG];// minw[i][j]:节点i到2^j级祖先路径上的最小边权vector<node2>g[N];// 最大生成树的邻接表boolvis[N];// BFS访问标记// BFS预处理深度、父节点和最小边权voidbfs(intstart){queue<int>q;q.push(start);d[start]=1;// 根节点深度为1vis[start]=true;while(!q.empty()){intu=q.front();q.pop();// 遍历所有邻接节点for(autox:g[u]){intv=x.to;intw=x.w;if(d[v])continue;// 已访问过d[v]=d[u]+1;// 深度+1f[v][0]=u;// 父节点minw[v][0]=w;// 到父节点的边权vis[v]=true;q.push(v);}}}// 查询从s到e路径上的最大载重(最小边权的最大值)intquery(ints,inte){// 检查是否连通if(find(s)!=find(e))return-1;// 保证s的深度不小于eif(d[s]<d[e])swap(s,e);intres=INF;// 将s提升到与e同一深度，并记录路径上的最小边权for(inti=LOG-1;i>=0;i--){if(d[f[s][i]]>=d[e]){res=min(res,minw[s][i]);s=f[s][i];}}// 如果此时s==e，说明e是s的祖先if(s==e)returnres;// 同时提升s和e，直到它们的父节点相同for(inti=LOG-1;i>=0;i--){if(f[s][i]!=f[e][i]){res=min(res,min(minw[s][i],minw[e][i]));s=f[s][i];e=f[e][i];}}// 最后还要比较到LCA的两条边res=min(res,min(minw[s][0],minw[e][0]));returnres;}intmain(){cin>>n>>m;// 读入所有道路for(inti=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].z;}// 按限重降序排序sort(a+1,a+m+1,cmp);// 初始化并查集for(inti=1;i<=n;i++)fa[i]=i;// 构建最大生成树for(inti=1;i<=m;i++){intu=a[i].x;intv=a[i].y;intw=a[i].z;if(find(u)!=find(v)){unionSet(u,v);// 在生成树中添加边g[u].push_back({v,w});g[v].push_back({u,w});}}// 对每个连通分量进行BFS预处理for(inti=1;i<=n;i++){if(!vis[i]){bfs(i);}}// 倍增预处理：计算f和minw数组for(intk=1;k<LOG;k++){for(inti=1;i<=n;i++){f[i][k]=f[f[i][k-1]][k-1];minw[i][k]=min(minw[i][k-1],minw[f[i][k-1]][k-1]);}}// 处理查询cin>>q;while(q--){intx,y;cin>>x>>y;cout<<query(x,y)<<endl;}return0;}

满分代码：功能分析

算法思路

问题转化：将货车运输问题转化为在最大生成树上求两点间路径最小边权的问题
最大生成树：使用Kruskal算法构建最大生成树，保证任意两点间的路径具有最大的最小边权
LCA优化：使用倍增法预处理树结构，实现O(logN)的路径查询

核心步骤

预处理阶段：
- 读入数据并排序
- 构建最大生成树
- BFS预处理深度和父节点
- 倍增预处理祖先和路径最小值
查询阶段：
- 检查连通性
- 通过LCA找到路径上的最小边权

时间复杂度

每次查询：O(logN)，N最大10000
查询次数q最多 30,000
最坏情况复杂度：O(q × logN)

算法优势

利用最大生成树保证最优解
使用LCA倍增法实现快速查询
能够处理不连通的情况

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

信奥赛C++提高组csp-s之倍增算法思想及应用案例（4）