算法1

扩展域并查集 + 贪心

C++ 代码

/**
 * 扩展域并查集
 * 贪心
 */

#include <bits/stdc++.h>

using namespace std;
const int maxn = 20005, maxm = 100005;

int n, m, fa[maxn * 2];

struct Edge{
    int x, y, z;
}e[maxm];

bool cmp(Edge x, Edge y){
    return x.z > y.z;
}

int findfa(int x){
    if(x == fa[x]) return x;
    return fa[x] = findfa(fa[x]);
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; ++ i)
        cin >> e[i].x >> e[i].y >> e[i].z;
    sort(e, e + m, cmp);

    for(int i = 1; i <= 2 * n; ++ i) fa[i] = i;

    for(int i = 0; i < m; ++ i){
        int fx = findfa(e[i].x), fy = findfa(e[i].y);
        if(fy == fx){
            cout << e[i].z << endl;
            return 0;
        }
        fa[fx] = findfa(e[i].y + n);
        fa[fy] = findfa(e[i].x + n);
    }
    cout << 0 << endl;
    return 0;
}

算法2

二分图判定 + 二分

C++ 代码

/**
二分图判定 + 二分
*/
#include <bits/stdc++.h>

using namespace std;

int n, m;

const int maxn = 40005, maxm = 100005;
int head[maxn], ver[2 * maxm], Next[2 * maxm], tot, v[maxn], edge[2 * maxm];
int a[maxm];

void add(int x, int y, int z){
    ver[++ tot] = y, edge[tot] = z;
    Next[tot] = head[x], head[x] = tot;
}

bool dfs(int x, int color, int limit){
    v[x] = color;
    for(int i = head[x]; i; i = Next[i]){
        if(edge[i] <= limit) continue;
        int y = ver[i];
        if(!v[y]){
            bool flag = dfs(y, 3 - color, limit);
            if(!flag) return false;
        }
        else if(v[y] == color) return false;
    }
    return true;
}

bool check(int val){
    memset(v, 0, sizeof(v));
    //染色法判断二分图
    for(int i = 1; i <= n; ++ i)
        if(!v[i])
            if(!dfs(i, 1, val)) return false;
    return true;
}

int main()
{
    cin >> n >> m;
    a[0] = 0;
    for(int i = 1, x, y, z; i <= m; ++i){
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
        a[i] = z;
    }
    sort(a, a + 1 + m);

    int l = 0, r = m;
    while(l < r){
        int mid = l + r >> 1;
        if(check(a[mid])) r = mid;
        else l = mid + 1;
    }
    cout << a[l] << endl;
    return 0;
}