博客

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








#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cmath>

#define mxn 20000+5
#define mxm 100000+5
#define loc

using namespace std;

int n,m;
int f[mxm];

struct Nd
{
       int a,b;
       int ht;
       bool operator<(const Nd &Nxt)const
       {
            return Nxt.ht<ht;
       }
}r[mxm];

int fd(int x)
{
    if (f[x]==x) return x;
    f[x]=fd(f[x]);
    return f[x];
}

int mrg(int x,int y)
{
    int rx=fd(x),ry=fd(y);
    f[rx]=ry;
}

int main()
{
    #ifdef loc
    freopen("prison.in","r",stdin);
    freopen("prison.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&r[i].a,&r[i].b,&r[i].ht); 
    }
    
    sort(r+1,r+m+1);
    
    for (int i=1;i<=n*2+1;++i) f[i]=i;
    
    for (int i=1;i<=m;++i)
    {
        int ra=fd(r[i].a),rb=fd(r[i].b),ba=fd(r[i].a+n),bb=fd(r[i].b+n);
        
        if (ra==rb)
        {
                   printf("%d",r[i].ht);
                   return 0;
        }
        
        mrg(ra,bb);
        mrg(rb,ba);        
    }   
    
    printf("0");
    return 0;
}