信奥赛C++提高组csp-s之并查集（案例实践）2

信奥赛C++提高组csp-s之并查集（案例实践）2

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了t tt区，而自己在s ss区。

该市有m mm条大道连接n nn个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从s ss至t tt的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的n nn，m mm，s ss，t tt，其含义见【题目描述】。

接下来m mm行，每行三个整数u , v , w u, v, wu,v,w，表示有一条大道连接区u uu和区v vv，且拥挤度为w ww。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

输入输出样例 1

输入 1

3 3 1 3 1 2 2 2 3 1 1 3 3

输出 1

2

数据规模与约定

• 对于30 % 30\%30%的数据，保证n ≤ 10 n\leq 10n≤10。
• 对于60 % 60\%60%的数据，保证n ≤ 100 n\leq 100n≤100。
• 对于100 % 100\%100%的数据，保证1 ≤ n ≤ 10 4 1 \leq n\leq 10^41≤n≤104，1 ≤ m ≤ 2 × 10 4 1 \leq m \leq 2 \times 10^41≤m≤2×104，w ≤ 10 4 w \leq 10^4w≤104，1 ≤ s , t ≤ n 1 \leq s, t \leq n1≤s,t≤n。且从s ss出发一定能到达t tt区。

样例输入输出 1 解释

小明的妈妈要从1 11号点去3 33号点，最优路线为1 11->2 22->3 33。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,m,s,t,ans;structedge{intx,y,w;// 边的两个端点和拥挤度}a[20010];intfa[10010];// 并查集数组// 并查集查找根节点（带路径压缩）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;}// 检查当拥挤度限制为mid时，s和t是否连通boolcheck(intmid){// 初始化并查集for(inti=1;i<=n;i++)fa[i]=i;// 遍历所有边，将拥挤度不超过mid的边加入图中for(inti=1;i<=m;i++){if(a[i].w<=mid){unionSet(a[i].x,a[i].y);}}// 检查s和t是否连通returnfind(s)==find(t);}intmain(){cin>>n>>m>>s>>t;// 读入所有边for(inti=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].w;}// 二分查找最小的最大拥挤度intl=1,r=1e4;// 拥挤度范围是1-10000while(l<=r){intmid=(l+r)/2;if(check(mid)){// 如果当前mid能满足条件，尝试更小的值ans=mid;r=mid-1;}else{// 如果当前mid不能满足条件，需要更大的值l=mid+1;}}cout<<ans;return0;}

功能分析

这个程序解决的是"最小化路径上最大拥挤度"的问题，采用了二分答案 + 并查集的方法。

核心思路

1. 问题转化：寻找从s到t的一条路径，使得路径上所有边的最大拥挤度最小
2. 二分策略：对拥挤度的可能取值进行二分，检查某个拥挤度限制下s和t是否连通
3. 连通性检查：使用并查集来高效判断在只使用拥挤度不超过某值的边时，s和t是否连通

算法步骤

1. 输入处理：读取图的节点数、边数、起点和终点，以及所有边的信息

2. 二分查找：

   • 左边界l=1，右边界r=10000（题目保证w≤10000）
   • 对于每个中间值mid，检查在只使用拥挤度≤mid的边时，s和t是否连通

3. 连通性检查(check函数)：

   • 初始化并查集，每个节点自成一个集合
   • 遍历所有边，将拥挤度不超过mid的边连接的两个节点合并
   • 最后检查s和t是否在同一个集合中

4. 结果输出：输出满足条件的最小拥挤度

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

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

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、csp高频考点知识详解及案例实践：
  • CSP信奥赛C++之动态规划
  • CSP信奥赛C++之标准模板库STL
• 四、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

---

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

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

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

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

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

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

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

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

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

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

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

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

· 文末祝福 ·

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