二分法

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
using ll=long long;

struct Edge
{
    int u,v,nxt;
}edges[200002];

struct Person
{
    int u,v;
    ll c;
}ps[200005];

int head[100001];
int color[100001];
int tot;
int n,m;

inline void add_edge(int u, int v)
{
    edges[++tot].nxt=head[u];
    head[u]=tot;
    edges[tot].v=v;
    edges[tot].u=u;
}

bool dfs(int p, int c)
{
    color[p]=c;
    for(int i=head[p]; i; i=edges[i].nxt)
    {
        int v=edges[i].v;
        if(color[v]==0)
        {
            if(!dfs(v, 3-c))
                return false;
        }
        else if(color[v]==c)
            return false;
    }
    return true;
}

bool is_ok(ll v)
{
    tot=0;
    memset(head,0,sizeof head);

    for(int i=1; i<=m; ++i)if(ps[i].c > v)
    {
        int u=ps[i].u;
        int v=ps[i].v;
        add_edge(u,v);
        add_edge(v,u);
    }

    memset(color, 0, sizeof color);
    for(int i=1; i<=n; ++i)
    {
        if(color[i]==0)
        {
            if(!dfs(i, 1))return false;
        }
    }

    return true;
}


int main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;

    ll low=0,high=0;
    for(int i=1; i<=m; ++i)
    {
        cin>>ps[i].u>>ps[i].v>>ps[i].c;
        high=max(high, ps[i].c);
    }

    while(low<high)
    {
        ll mid=(low+high)>>1;
        if(is_ok(mid))high=mid;
        else low=mid+1;
    }

    cout<<low<<endl;

    return 0;
}