MyException - 我的异常网
当前位置:我的异常网» 编程 » 看押罪犯-并查集操作

看押罪犯-并查集操作

www.MyException.Cn  网友分享于:2015-03-13  浏览:0次
关押罪犯---并查集操作
题目描述 Description

S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极

不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨

气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之

间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并

造成影响力为c 的冲突事件。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,

然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,

如果影响很坏,他就会考虑撤换警察局长。

在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在

两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只

要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那

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

输入描述 Input Description

第一行为两个正整数N 和M,分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的M 行每行为三个正整数aj,bj,cj,表示aj 号和bj 号罪犯之间存在仇恨,其怨气值为cj。数据保证且每对罪犯组合只出现一次。

输出描述 Output Description

共1 行,为Z 市长看到的那个冲突事件的影响力。如果本年内监狱

中未发生任何冲突事件,请输出0。

样例输入 Sample Input

4 6

1 4 2534

2 3 3512

1 2 28351

1 3 6618

2 4 1805

3 4 12884

样例输出 Sample Output

3512

数据范围及提示 Data Size & Hint

罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,市长看到的冲突事件

影响力是3512(由2 号和3 号罪犯引发)。其他任何分法都不会比这个分法更优。

【数据范围】

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

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

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

这题最简便的方法我认为就是克鲁斯卡尔思想的并查集操作

我们将敌对关系看做边,将罪犯看做两个点,将怨气值看做边的权值

然后我们按照怨气值从大到小排序,但是这里有一个问题

就是要将两个点分到不同集合,等找到不能分到不同集合的点就找到了答案停止搜索

但是我们一般的并查集是查找在同一集合简便,所以我们要将点做一个映射

假设A点与B点是敌对关系,我们就将A点与B点的映射放在同一个集合里,B点与A点的映射放在同一集合里

这时如果A点所在的集合与B点所在的集合为同一集合,那么他们将不能放在两个不同的监狱,

又因为我们是按照怨气值从大到小排序,所以他们的结果是最优的

#include<cstdio>
#include<algorithm>
using namespace std;
struct Node{
	int a;
	int b;
	int angry;
}a[100005];
int pa[200005];
bool cmp(Node a, Node b){
	return a.angry > b.angry;
}
int find(int x){
	return pa[x] == x ? x : find(pa[x]);
}
int main(){
	int n, m, i;
	scanf("%d%d", &n, &m);
	for (i = 0; i < m; i++){
		scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].angry);
	}
	for (i = 0; i <= n * 2; i++)
		pa[i] = i;
	sort(a, a + m, cmp);
	for (i = 0; i < m; i++){
		int x = find(a[i].a);
		int y = find(a[i].b);
		if (x == y){
			printf("%d\n", a[i].angry);
			break;
		}
		pa[x] = find(a[i].b + n);
		pa[y] = find(a[i].a + n);
	}
	if (i == m)
		printf("0\n");
	return 0;
}


文章评论

初级 vs 高级伟德国际app者 哪个性价比更高?
初级 vs 高级伟德国际app者 哪个性价比更高?
我是如何打败拖延症的
我是如何打败拖延症的
Web伟德国际app者需具备的8个好习惯
Web伟德国际app者需具备的8个好习惯
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
60个伟德国际app者不容错过的免费资源库
60个伟德国际app者不容错过的免费资源库
10个调试和排错的小建议
10个调试和排错的小建议
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
程序员都该阅读的书
程序员都该阅读的书
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
漫画:程序员的工作
漫画:程序员的工作
Web伟德国际app人员为什么越来越懒了?
Web伟德国际app人员为什么越来越懒了?
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
鲜为人知的编程真相
鲜为人知的编程真相
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
如何成为一名黑客
如何成为一名黑客
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
总结2014中国互联网十大段子
总结2014中国互联网十大段子
老程序员的下场
老程序员的下场
代码女神横空出世
代码女神横空出世
编程语言是女人
编程语言是女人
旅行,写作,编程
旅行,写作,编程
每天工作4小时的程序员
每天工作4小时的程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
我的丈夫是个程序员
我的丈夫是个程序员
程序员必看的十大电影
程序员必看的十大电影
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员的鄙视链
程序员的鄙视链
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
中美印日四国程序员比较
中美印日四国程序员比较
Java程序员必看电影
Java程序员必看电影
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
一个程序员的时间管理
一个程序员的时间管理
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
软件伟德国际app程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有