当前位置:首页 > 并查集 > 正文
SSOJ1306关押罪犯(NOIP2010)
1335+

题目大意:n名罪犯有m个怨恨关系;只有2个监狱,怎么安排才能使监狱中的罪犯怨恨小些?最小的那个怨恨值是多少?

题目描述

S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使Z 市长看到的那个冲突事件的影响力最小?这个最小值是少?

输入

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

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

输出

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

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

样例输入

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

样例输出

3512

提示

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

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

【数据范围】

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

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

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

NOIP2010提高组第三题

解题思路

如果是安排在同一个监狱,那么用并查集合并是非常方便的,但现在有怨恨的要安排在两个不同的监狱,能“反合并”吗?很麻烦!

不妨转换一下思考方向,怎样的罪犯会安排在同一个监狱呢?如果两个罪犯,都与另外一个罪犯有怨恨关系,那么这两个罪犯就可以放在同一个监狱,用并查集合并在一起。现在有n个罪犯,建立一个f数组,前n个元素表示罪犯自己,后n个元素表示罪犯的敌人,如果a和b有怨恨关系,那么a和b的敌人合并在一起,即合并a和b+n,同样b和a的敌人也合并在一起,即合并b和a+n。

现在要求怨恨值最小,我们可以先处理怨恨值大的罪犯,这样一直处理下去,直到发现两个有怨恨的罪犯在同一个监狱,就输出该对罪犯的怨恨值;如果找不到,就输出0。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

SSOJ1306关押罪犯(NOIP2010):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter