信奥赛C++提高组csp-s之并查集（案例实践）4-程序员充电站

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

题目描述

S 城现有两座监狱，一共关押着N NN名罪犯，编号分别为1 ∼ N 1\sim N1∼N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c cc的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c cc的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了N NN名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

每行中两个数之间用一个空格隔开。第一行为两个正整数N , M N,MN,M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M MM行每行为三个正整数a j , b j , c j a_j,b_j,c_jaj,bj,cj，表示a j a_jaj号和b j b_jbj号罪犯之间存在仇恨，其怨气值为c j c_jcj。数据保证1 ≤ a j < b j ≤ N , 0 < c j ≤ 10 9 1\le a_j< b_j\leq N, 0 < c_j\leq 10^91≤aj<bj≤N,0<cj≤109，且每对罪犯组合只出现一次。

输出格式

共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

输入输出样例 #1

输入 #1

4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884

输出 #1

说明/提示

输入输出样例说明

罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是3512 35123512（由2 22号和3 33号罪犯引发）。其他任何分法都不会比这个分法更优。

数据范围

对于30 % 30\%30%的数据有N ≤ 15 N\leq 15N≤15。

对于70 % 70\%70%的数据有N ≤ 2000 , M ≤ 50000 N\leq 2000,M\leq 50000N≤2000,M≤50000。

对于100 % 100\%100%的数据有N ≤ 20000 , M ≤ 100000 N\leq 20000,M\leq 100000N≤20000,M≤100000。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,m;// n:罪犯数量，m:仇恨关系数量intfa[40010];// 并查集数组，大小为2*n，用于表示每个罪犯的两个"域"structnode{intx,y,w;// 仇恨关系：x和y罪犯之间的怨气值为w}a[100010];// 存储所有仇恨关系// 比较函数：按怨气值从大到小排序boolcmp(node a,node b){returna.w>b.w;}// 并查集查找函数（带路径压缩）intfind(intx){if(fa[x]!=x)returnfa[x]=find(fa[x]);// 路径压缩returnfa[x];}// 并查集合并函数voidunionSet(intx,inty){introotx=find(x);introoty=find(y);if(rootx==rooty)return;// 已在同一集合，无需合并fa[rooty]=rootx;// 合并集合}intmain(){cin>>n>>m;// 读入所有仇恨关系for(inti=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].w;}// 按怨气值从大到小排序（贪心策略）sort(a+1,a+m+1,cmp);// 初始化并查集，每个罪犯有两个域：自身和对应的"敌人域"for(inti=1;i<=2*n;i++){fa[i]=i;}// 处理每条仇恨关系（从怨气值最大的开始）for(inti=1;i<=m;i++){// 如果两个罪犯已经在同一集合，说明他们必须关在同一监狱// 此时当前怨气值就是无法避免的最大冲突if(find(a[i].x)==find(a[i].y)){cout<<a[i].w;return0;}else{// 将x与y的敌人域合并，表示x和y不能在同一监狱unionSet(a[i].x,a[i].y+n);// 将y与x的敌人域合并，对称操作unionSet(a[i].y,a[i].x+n);}}// 所有关系处理完都没有冲突，输出0cout<<0;return0;}

功能分析

核心思路

使用扩展域并查集来维护罪犯之间的对立关系：

每个罪犯i有两个域：i（自身）和i+n（敌人域）
如果两个罪犯x和y有仇恨，就把x与y+n合并，y与x+n合并
这表示x和y不能在同一监狱

算法流程

输入处理：读取罪犯数量和仇恨关系
贪心排序：按怨气值从大到小排序，优先处理怨气值大的冲突
并查集初始化：每个罪犯初始化两个独立的域
冲突检测：
- 如果两个罪犯已在同一集合，说明他们必须关在一起，当前怨气值就是答案
- 否则，建立对立关系，确保他们不会在同一监狱
输出结果：如果没有冲突，输出0

关键技巧

扩展域：通过为每个罪犯创建两个域来模拟"在同一监狱"和"在不同监狱"的关系
贪心策略：优先解决怨气值大的冲突，确保大的冲突被避免
提前终止：一旦发现无法避免的冲突就立即输出结果

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

#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
- 信奥赛C++提高组csp-s知识详解及案例实践
四、考级、竞赛刷题题单及题解：
- 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 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.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;}

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