【NOIP2010提高组 关押罪犯】

题目背景

NOIP2010提高组试题

题目描述

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≤1,000,000,000,且每对罪犯组合只出现一次。

输出格式

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

样例数据 1

输入

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。

一看到最大值最小,立马想到二分,然后看了下代码长度,感觉还是冷静一下吧……其实仔细想想,分集合这种事情不是很像并查集干的事情么!我们要把最大的冲突降到最小,那么就得尽力把影响大的罪犯分到两个牢房里,于是把影响力当边权从大到小排序,然后开始做并查集,如果这条边的两个端点不在一个集合中(跟前面没矛盾),就把(a,b+n)分一个集合中,(a+n,b)分一个集合中,如果两个端点在一个集合中,说明这就是最优解了,因为如果满足它,那前面某个影响力更大的事件的两个罪犯就分不到两个监狱去,就不是最优解了。所以找到这条边再输出边权即可。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*