【Luogu1525】关押罪犯

Source and Judge

NOIP2010 提高组 T3
Luogu1525
Caioj1543

Problem

【Brief description】
S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。
很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。
我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,
怨气值越大,则这两名罪犯之间的积怨越多。
如果两名怨气值为c 的罪犯被关押在同一监狱,
他们俩之间会发生摩擦,并造成影响力为 c 的冲突事件。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,
然后上报到S 城Z 市长那里。
公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。
他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。
假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。

那么,应如何分配罪犯,才能使Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少?
【Input】
每行中两个数之间用一个空格隔开。第一行为两个正整数 N 和 M,分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的 M 行每行为三个正整数aj,bj,cj,表示 aj 号和 bj 号罪犯之间存在仇恨,其怨气值为cj。
【Output】
共1 行,为Z 市长看到的那个冲突事件的影响力。
如果本年内监狱中未发生任何冲突事件,请输出0。
【Limited conditions】
数据保证1<=aj<=bj<=N,0<cj≤1,000,000,000,且每对罪犯组合只出现一次。
对于30%的数据有N≤ 15。
对于70%的数据有N≤ 2000,M≤ 50000。
对于100%的数据有N≤ 20000,M≤ 100000。
【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
【Sample explanation】
罪犯之间的怨气值如下面左图所示,右图所示为罪犯的分配方法,
市长看到的冲突事件影响力是3512(由 2 号和 3 号罪犯引发)。
其他任何分法都不会比这个分法更优。

Record

30min

Analysis

请先思考后再展开

考虑一个贪心:优先处理权值大的关系
证明:因为本题求的是最大值,如果放弃当前,那么无论你后面多么优秀,答案都是确定的
然后因为要维护互斥的关系,可以很巧妙地用拆点解决,然后就可以并查集了

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
int fa[41000];
int findfa(int x) {return fa[x]=(fa[x]==x?x:findfa(fa[x]));}
struct Edge
{
int x,y,c;
}e[110000];
bool cmp(Edge a,Edge b) {return a.c>b.c;}
void main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n*2;i++) fa[i]=i;
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
int x=e[i].x,y=e[i].y;
int fx=findfa(x),fy=findfa(y);
if(fx==fy) {printf("%d",e[i].c);return;}
fa[fx]=findfa(y+n);
fa[fy]=findfa(x+n);
}
puts("0");
}
};
int main()
{
mine::main();
}

Analysis2

请先思考后再展开

也可以二分答案,然后对于大于mid的边,判断是否是二分图

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8b22.html
转载请注明出处,谢谢!