博客

题目描述

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

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

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

那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入输出格式

输入格式：

 

每行中两个数之间用一个空格隔开。第一行为两个正整数 N,MN,M ，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 MM 行每行为三个正整数 a_j,b_j,c_jaj​,bj​,cj​ ，表示 a_jaj​ 号和 b_jbj​ 号罪犯之间存在仇恨，其怨气值为 c_jcj​ 。数据保证 1<aj≤bj≤N ,0 < cj≤ 1,000,000,0001<aj≤bj≤N,0<cj≤1,000,000,000 ，且每对罪犯组合只出现一次。

 

输出格式：

 

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

 

输入输出样例

输入样例#1： 

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

输出样例#1： 

3512

说明

【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 35123512 （由 22 号和 33 号罪犯引发）。其他任何分法都不会比这个分法更优。

【数据范围】

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

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

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

 

Solution:

　　水题，直接贪心+并查集（当然也可以二分答案+二分图染色判定）。

　　贪心的想到，我们尽可能的将冲突值大的两者放到不同的监狱里，先将冲突值从大到小排序，由于敌人的敌人就是我的朋友，于是每次就并查集合并一下同类的关系，当某次出现冲突时，当前的冲突值就是最少的。

代码：

 

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=200005;
int n,m,fa[N];
struct node{
    int to,fr,v;
    bool operator < (const node a) const {return v>a.v;} 
}e[N];

il int gi(){
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
    return f?-a:a;
}

il int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}

int main(){
    n=gi(),m=gi();
    For(i,1,n<<1|1) fa[i]=i;
    For(i,1,m) e[i].fr=gi()+1,e[i].to=gi()+1,e[i].v=gi();
    sort(e+1,e+m+1);
    int fx,fy;
    For(i,1,m) {
        fx=find(fa[e[i].fr]),fy=find(fa[e[i].to]);
        if(fx==fy) cout<<e[i].v,exit(0);
        if(fx!=fy) {
            fa[find(fx+n)]=fy;
            fa[find(fy+n)]=fx;
        }
    }
    cout<<0;
    return 0;
}