二进制枚举$(40pts\ n^2*2^n)$

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int g[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    int res=1e9;
    for(int i=1;i<=m;i++) //储存两个人之间的怒气值
    {
        int a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        g[a][b]=g[b][a]=c;
    }
    for(int i=0;i<1<<n;i++) //枚举每种分发
    {
        vector<int> a,b; //分别储存两个监狱的人
        for(int j=0;j<n;j++)
        {
            if(i>>j&1) a.push_back(j); //第一个监狱
            else b.push_back(j); //第二个监狱
        }
        int maxv=0; //同一个监狱里面的最大值是多少
        for(int j=0;j<a.size();j++) //枚举第一个监狱的第一个人
        {
            for(int k=j+1;k<a.size();k++) //枚举第一个监狱里面的第二个人
            {
                maxv=max(maxv,g[a[j]][a[k]]);
            }
        }
        for(int j=0;j<b.size();j++) //枚举第二个监狱里的第一个人
        {
            for(int k=j+1;k<b.size();k++) //枚举第二个监狱里面的第二个人
            {
                maxv=max(maxv,g[b[j]][b[k]]);
            }
        }
        res=min(res,maxv); //尝试使用当前方案去更新答案
    }
    cout<<res;
    return 0;
}

二分答案+染色法判定二分图$((N+M)logC)$

将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。 那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在 $[0,10^9]$之间枚举最大边权 $limmit$，当 $limit$ 固定之后，剩下的问题就是: 判断能否将所有点分成两组，使得所有权值大于$limmit$ 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 $limmit$ 的边构成的新图是否是二分图。

判断二分图可以用染色法，时间复杂度是 $O(N+ M)$，其中 $N$ 是点数，$M$ 是边数，

#include<bits/stdc++.h>
using namespace std;
const int N=20010,M=200010;
int h[N],e[M],ne[M],w[M],idx;
int color[N]; //二分图染色
int n,m;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool dfs(int u,int c,int mid)
{
    color[u]=c;//u染成点c
    for(int i=h[u];i!=-1;i=ne[i]) //遍历u的所有邻点
    {
        if(w[i]<=mid) continue;//需要忽略的边
        int j=e[i];
        if(color[j]==0)
        {
            if(!dfs(j,3-c,mid)) return false;
            //染成相反的颜色发生了冲突
        }
        else if(color[j]==c) //邻点和当前颜色冲突
        {
            return false;
        }
    }
    return true;
}
bool check(int mid)
{
    memset(color,0,sizeof color);//清空颜色
    for(int i=1;i<=n;i++)
    {
        if(color[i]==0) //还没有染色
        {
            if(!dfs(i,1,mid)) return false;
            //染色出现冲突
        }
    }
    return true; //可以成功染色
    //也就是可以在边权小于等于mid的情况下，
    //存在所有的事件影响力都不超过mid的方案
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}