洛谷1525 关押罪犯NOIP2010 并查集
2024-08-28 08:18:34
问题描述
S城现有两座监狱,一共关押着N名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c的冲突事件。每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。在详细考察了N名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使Z市长看到的那个冲突事件的影响力最小?这个最小值是多少?
此题各种做法都有,但最简单的方法还是并查集。开一个两倍的并查集表示犯人的集合及其补集,排序按怨念从大到小往集合里放,发现冲突直接输出就可以了。
排序直接调用的<algorithm>中的 sort(a, a+n)。并查集是标准的一行式路径压缩,每次查找确认不冲突后分别放到对方的补集中。空间 O(2n),时间 O(m lg*n),其中 lg*n 最大为 5 效率很高,90分。
最后注意没有冲突要输出 0,这样才能 100 分。
有些题库可能用cin和cout会导致超时
并查集,食物链的削弱版
//洛谷1525 关押罪犯 并查集
#include<bits/stdc++.h>
using namespace std;
struct node{
int a,b,c;
}p[];
int n,m;
int f[];
bool cmp(node a,node b){
return a.c>b.c;
}
int find(int x){
if(x==f[x])return x;
else return find(f[x]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
}
for(int i=;i<=*n;i++){
f[i]=i;
}
sort(p+,p+m+,cmp);
for(int i=;i<=m;i++){
int x=find(p[i].a);int y=find(p[i].b);
if(x==y){
cout<<p[i].c;
return ;
}
f[y]=find(p[i].a+n);
f[x]=find(p[i].b+n);
}
cout<<;
return ;
}
最新文章
- html5 前端图片处理(预览、压缩、缩放)
- 在sql server中利用with as实现递归功能
- net 调用https接口
- Android fragment 想activity 传送数据
- html5 拖拽的简要介绍
- JBOSS尝鲜
- 自定义带弹性效果的pageControl
- 创建采购订单批到程序用的BAPI
- 个推A/B测试评测
- 睡不着,复习一下C++基础中的基础(深拷贝与浅拷贝)
- 初识SQL Server2017 图数据库(一)
- (二十七)QQ好友列表的实现
- 用ASP.NET Core 2.0 建立规范的 REST API
- django----Form实时更新两种方式
- Nginx+keepalived 双机热备(主从模式)
- C++学习(二)之Visual Studio写system语句 生成可执行文件
- 2.select查询用法
- November 01st, 2017 Week 44th Wednesday
- 每一个JavaScript开发者应该了解的浮点知识
- 第二章 mybatis使用注解实现in查询(mysql)