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

输出格式

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

样例输入

C++

1 2 3 4 5 6 7

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

样例输出

C++

1

3512

限制

每个测试点1s

提示

分配方法：市长看到的冲突事件影响力是3512（由2号和3号罪犯引发）。其他任何分法都不会比这个分法更优。

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

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

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

题解

此题各种做法都有，但最简单的方法还是并查集。开一个两倍的并查集表示犯人的集合及其补集，排序按怨念从大到小往集合里放，发现冲突直接输出就可以了。

排序直接调用的<algorithm>中的 sort(a, a+n)。并查集是标准的一行式路径压缩，每次查找确认不冲突后分别放到对方的补集中。空间 O(2n)，时间 O(m lg*n)，其中 lg*n 最大为 5 效率很高，90分。

最后注意没有冲突要输出 0，这样才能 100 分。

有些题库可能用cin和cout会导致超时

以删边的方式看哪些边删掉后能成为二分图，删掉的最大边就为答案。

将所有边排序，进行二分猜答案，猜小于等于哪条边的删掉后为二分图，再进行验证。

#include<iostream>

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int maxn=20005;
struct shu
{
int u,v,l;
};
int n,m,T;
vector<int>a[maxn],w[maxn];
vector<shu>e;
int color[maxn];


bool my(shu a,shu b)
{
return a.l<b.l;
}
void init()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x].push_back(y);
a[y].push_back(x);

w[x].push_back(z);
w[y].push_back(z);
e.push_back((shu){x,y,z});
}
sort(e.begin(),e.end(),my);
}


bool bfs(int p,int z)
{
queue<int>q;
q.push(p);
color[p]=1;
while(!q.empty())
{
int t=q.front();
q.pop();
for(int i=0;i<a[t].size();i++)
{
int j=a[t][i];
if(w[t][i]<=z) continue;
if(color[j]==color[t]) return 0;
if(color[j]==0) 
{
q.push(j);
color[j]=3-color[t];
}
}
}
return 1;
}
bool check(int x)
{
memset(color,0,sizeof(color));
for(int i=1;i<=n;i++) if(color[i]==0)
{
bool ok=bfs(i,x);
if(ok==0) return 0;
}
return 1;
}
int main()
{
init();

if(check(0)) 
{
printf("0");
return 0;
}
int a=0,b=e.size(),ans=0;
while(a<=b)
{
int c=(a+b)/2;
if(check(e[c].l))
{
ans=e[c].l;
b=c-1;
}
else a=c+1;
}
printf("%d",ans);
    return 0;
}