并查集+贪心

本题的核心在于寻找奇环中权值最小的边的最大值，我们当然可以按照二分+搜索判定的方式求解，但是如果我们熟悉最小生成树的算法，我们显然可以想到最小生成树中如何判断新添加的边是否形成环的问题。同理我们也可以按照边从大到小的顺序排列边，然后用并查集判断是否形成环。
当然到这里为止大家都可以想到，问题在于我们的并查集并不能确定形成的环到底是奇环还是偶环，因为只有奇环才是真正限制我们操作的。
这里我们就要用到图遍历里面的另一个知识了，也即增广路的知识，按照敌人的敌人就是队友的思想，实际上添加到一个并查集的就是敌人的敌人，为了实现这个目标，我们需要把敌人的关系记录下来，怎么记录呢？我们不能真的把两个具有敌人关系的节点加入到同一个并查集中，因为这种方式下，敌人和朋友实际上都被添加到了同一并查集中，对于偶环我们也会得到在同一个并查集的结果，所以为了避免这种现象，又能合理地保存敌人关系，我们将每个节点的敌人节点设置为一个虚拟节点，它不具有实际的性质，只是一个联系两个朋友的纽带。
也即我们假设每个节点都有一个虚拟节点，那么如果这两个点不在一个监狱，我们就将这两个点分别和对方的虚拟节点加入到同一个并查集中，用来标示一个虚拟的敌人的关系，例如对于a,b两个节点，他们有虚拟节点a’,b’，如果这两者不在同一个监狱，那么我们将得到并查集(a,b’),(b,a’)，接着如果我们有关系b,c出现，此时b,c仍然不在同一个监狱，但是a,c具有敌人的敌人的关系，那么，通过虚拟节点b’，c可以与a添加到同一并查集中，此时b所在的并查集为(b,a’),与c’合并为一个并查集后得到(b,a’,c’)，而c通过b’可以得到并查集(a,b’,c)，可见我们实现了敌人的敌人在同一个并查集的目标，然后，如果某个过程中两个人位于同一并查集，我们就可以判定，当前一定存在奇圈，而当前边恰好是不合法的最大值。我们直接输出即可。

时间复杂度O(n+m);

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N=40010;
int arr[N];

int find(int x){
    return x==arr[x]?x:arr[x]=find(arr[x]);
}
void merge(int x,int y){
    x=find(x);
    y=find(y);
    arr[x]=y;
    return ;
}

int main(){
    int n,m;
    cin>>n>>m;
    int u,v,w;
    vector<vector<int>> edge(m,vector<int>(3));
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        edge[i][0]=w;
        edge[i][1]=u;
        edge[i][2]=v;
    }
    sort(edge.begin(),edge.end(),[](vector<int>&a,vector<int>&b){
        return a[0]>b[0];
    });
    for(int i=1;i<N;i++)arr[i]=i;
    for(int i=0;i<m;i++){
        int x=edge[i][1];
        int y=edge[i][2];
        x=find(x);
        y=find(y);
        if(x==y){
            cout<<edge[i][0]<<endl;
            return 0;
        }
        //按照虚拟边关系进行并查集的合并。
        merge(edge[i][1]+n,y);
        merge(edge[i][2]+n,x);
    }
    cout<<0;
    return 0;

}

算法2

二分+判定 $O((n+m)logC)$

实现的技巧就是二分边权，便利时，我们用边权进行剪枝，对于小于mid的边权不要遍历，同时使用染色法判断是否有奇圈即可。

时间复杂度

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
const int M=200010;
int edge[M];
int nest[M];
int last[N];
int val[M];
int cnt=2;

void add(int u,int v,int w){
    edge[cnt]=v;
    nest[cnt]=last[u];
    last[u]=cnt;
    val[cnt]=w;
    cnt++;
    return;
}

//二分图染色判断奇圈
int vise[N];
int mid;
bool dfs(int k,int color){
    vise[k]=color;
    for(int i=last[k];i;i=nest[i]){
        //边权剪枝
        if(val[i]<mid)continue;
        if(!vise[edge[i]]){
            if(!dfs(edge[i],3-color))return false;
        }else{
            if(vise[k]==vise[edge[i]])return false;
        }
    }
    return true;
}
int main(){
    int n,m;
    cin>>n>>m;
    int u,v,w;
    vector<vector<int>> e(m,vector<int>(3));
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&u,&v,&w);
        e[i][0]=w;
        e[i][1]=u;
        e[i][2]=v;
        add(u,v,w);
        add(v,u,w);
    }
    int l=0;
    int r=1e9;
    int ans=0;
    for(;l<=r;){
        mid=(l+r)/2;
        memset(vise,0,sizeof(vise));
        bool tag=false;
        for(int i=1;i<=n;i++){
            if(!vise[i]){
                if(!dfs(i,1)){
                    tag=true;
                    break;
                }
            }
        }
        if(tag){
            ans=max(ans,mid);
            //此时最小边权应该更大一些
            l=mid+1;
        }else{
            //此时最小边权应该更小一些
            r=mid-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}