题目描述

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）交换一下，那么虽然A解决了，但是B没有解决，又因为我们是按照从大到小的顺序解决的所以B一定不小于A，因此最大矛盾值将增大，因此不交换的解更优
还有一点就是如何判断矛盾能否解决，这里作者太弱了，于是就用矛盾可以解决就加边的方式，如果2个点深度之和为偶数，那么矛盾就不可避免（这个比较好想），所以每次dfs就可以了
最后上代码
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<pair<int,int> >build;//用于排序，pair还是挺好用的，不会的话可以百度一下
int z[100002],x[100002],y[100002],deep[20002],vis[20002],head[20002];
int n,m,num;
struct hat
{
    int to;
    int next;
    int we;
}hate[200002];
void add(int fr,int to,int we)
{
    hate[++num].to=to;
    hate[num].we=we;
    hate[num].next=head[fr];
    head[fr]=num;
}//邻接链表储存
void dfs(int a,int dep)
{
    deep[a]=dep;
    vis[a]=1;
    for(int i=head[a];i!=0;i=hate[i].next)
    {
        if(!vis[hate[i].to])dfs(hate[i].to,dep+1);
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x[i],&y[i],&z[i]);
        build.push(make_pair(z[i],i));
    }
    int flag=1;
    while(flag&&!build.empty())
    {
        int se=build.top().second;
        build.pop();
        for(int i=1;i<=n;i++)vis[i]=0;
        dfs(x[se],1);
        if(vis[y[se]])
        {//矛盾不可调和部分
            if((deep[x[se]]+deep[y[se]])%2==0)
            {
                flag=0;
                printf("%d",z[se]);
            }
        }
        add(x[se],y[se],z[se]);
        add(y[se],x[se],z[se]);
    }
    if(flag==1)printf("0");//成功解决所有矛盾
}


来源：AK龙