博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
回档|NOIP2010 关押罪犯
阅读量:6690 次
发布时间:2019-06-25

本文共 1739 字,大约阅读时间需要 5 分钟。

描述

S城现有两座监狱,一共关押着N名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲 突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一 监狱,他们俩之间会发生摩擦,并造成影响力为c的冲突事件。每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。在详细考察了N名罪犯间的矛盾关系后,警察 局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间 有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使Z市长看到的那个冲突事件的影响力最小?这个最小值是多少?
格式
输入格式
输入文件的每行中两个数之间用一个空格隔开。
第一行为两个正整数N和M,分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M行每行为三个正整数aj,bj,cj,表示aj号和bj号罪犯之间存在仇恨,其怨气值为cj。
数据保证1<=aj<=bj<=N,0<=cj<=1000000000,且每对罪犯组合只出现一次。
输出格式
输出文件共1行,为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
限制
每个测试点1s
提示
分配方法:市长看到的冲突事件影响力是3512(由2号和3号罪犯引发)。其他任何分法都不会比这个分法更优。
对于30%的数据有N≤15。
对于70%的数据有N≤2000,M≤50000。
对于100%的数据有N≤20000,M≤100000。
解析:这道题,很容易想到用并差集解决。但就是写的拙不拙的问题了……俺就很拙,结果超时了。我的想法就是挂数。我是这样想的,用f[x]表示x罪犯的敌 人。如果两个罪犯都没有敌人,就互相做互相的敌人(不在同一个监狱),否则各自和对方的敌人做狱友。如果不能和对方的敌人做狱友,说明冲突了。我们又是先 排序了,因此这时就是最优解。
代码:

#include
#include
using namespace std;int f[40001];struct node{ int x,y,v;}e[20001];bool cmp(node a,node b){ return a.v>b.v;}int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}int main(){ int n,m; cin >> n >> m; for (int i=1; i<=m; i++) { cin >> e[i].x >> e[i].y >> e[i].v; } for (int i=1; i<=2*n; i++) f[i]=i; sort(e+1,e+m+1,cmp); for (int i=1; i<=m; i++) { int xx=find(e[i].x); int yy=find(e[i].y); if (xx==yy) { cout << e[i].v << endl; system("pause"); return 0;} f[xx]=find(e[i].y); f[yy]=find(e[i].x); } cout << 0;return 0;}

 

转载于:https://www.cnblogs.com/Shymuel/p/4393573.html

你可能感兴趣的文章
# 2017-2018-1 20155319 实验五 《通讯协议设计》
查看>>
通用后台管理系统(1)-数据库设计
查看>>
做自适应网页
查看>>
ACM的奇计淫巧_bitset优化
查看>>
centos 配置防火墙操作
查看>>
比亚迪速锐F3专用夏季座套 夏天坐垫 四季坐套
查看>>
Java web 实现 之 Filter分析ip统计网站的访问次数
查看>>
bzoj1303
查看>>
2013-2-1 pdf中无法用金山词霸取词问题
查看>>
2015.3.12 C#运用正则表达式点滴
查看>>
CSS布局自适应等分比例
查看>>
requests
查看>>
安装Git
查看>>
设置启动图片LaunchScreen 和 LaunchImage
查看>>
Ubuntu下搭建openGL开发环境
查看>>
ThreadLocal详解,处理成员变量线程不安全的情况
查看>>
四个简单易用的demo,关于iOS定时器和延时的,非常好用。
查看>>
通过Java语言连接mysql数据库
查看>>
1.简述Hibernate的工作原理。
查看>>
L84
查看>>