贴一个用并查集的，时间复杂度$O(mlogm)$

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20100, M = 100010;
int p[N], d[N];
struct Edge
{
    int a, b, c;
    bool operator<(const Edge e) const
    {
        return c > e.c; 
    }
}edge[M];

int find(int x)
{
    if (x != p[x])
    {
        int t = p[x];
        p[x] = find(p[x]);
        d[x] += d[t];
    }

    return p[x];
}

int main()
{
    int n, m;
    cin >> n >> m;

    int a, b, c;
    for (int i = 0; i < m; ++ i)
    {
        scanf("%d%d%d", &a, &b, &c);
        edge[i] = {a, b, c};
    }
    sort(edge, edge + m);

    for (int i = 1; i <= n; ++ i)
        p[i] = i;

    bool flag = true;
    for (int i = 0; i < m; ++ i)
    {
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            if ((d[a] - d[b] - 1) % 2 != 0)
            {
                cout << c << endl;
                flag = false;
                break;
            }
        }
        else
        {
            p[pa] = pb;
            d[pa] = d[b] - d[a] + 1;
        }
    }
    if (flag)
        cout << 0 << endl;

    return 0;
} 

tql

重载运算符这里和快排用的很妙

这里为什么还要sort啊？感觉没什么影响啊？

# Y总太强了

## ○|￣|_

是colour不是color，世界是用的英式英语

纠结这个不如多刷两个题

XD

y就是强

○|￣|_

#include<iostream> 
#include<algorithm> 
#include<vector>
#include<cstring>
const int Max=1e5+1;
using namespace std;
int hatred[Max];
int color[Max];
struct ele{
        int to,weight;
        ele(int a,int b){
            to=a,weight=b;  
        }
    };
vector<ele> v[Max];
void add(int a,int b,int c){
    ele tmp(b,c);
    v[a].push_back(tmp);
}
int Mid;
void print(int n){
    for(int i=1;i<=n;i++){
        cout<<color[i]<<" ";
    }
    cout<<endl;
}
bool dfs(int n,int c){
    //print(4);
    color[n]=c;
    //print(4);
    for(auto it=v[n].begin();it!=v[n].end();it++){
        if((*it).weight>hatred[Mid]){
        //  cout<<n<<(*it).to<<endl;
            if(color[(*it).to]==0){
            dfs((*it).to,3-c);
        }else{  
            if(color[(*it).to]==c){
                return false;
                }   
            } 
        }
    }
    return true;
}
int main(){
    int n,m;
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
        hatred[i]=c;
    }
    sort(hatred,hatred+1+m);
    int l=0,r=m;
    while(l!=r){
        Mid=(l+r)/2;
    //  cout<<l<<" "<<r<<" "<<hatred[Mid]<<endl;
        memset(color,0,sizeof(color));
        bool flag=false;
        for(int i=1;i<=n;i++){
            if(color[i]==0){
                //cout<<114;
                if(!dfs(i,1)){  
                    flag=true;
                    break;
                }
            }
        }
        //print(n);
        if(!flag){
            r=Mid;
        }else{
            l=Mid+1;
        }
        //cout<<l<<" "<<r<<endl;
    }
    Mid=(l+r)/2;
    cout<<hatred[Mid];
}/*
2 1
1 2 28135
*/

y总请问我这个做法问题在哪呢？谢谢

你的dfs函数的第一个if那里，应该写成 if(color[(it).to]==0){ if(!dfs((it).to,3-c)) return false};

谢谢！

y总太强了，学了半年就已经可以写出这个题了，我学了一年还是什么都不会

啊？真的吗，y总在哪说的呀请问

代码完全y风hh

说一下if (w[i] < limit) continue；和if (w[i] <= limit) continue；这两种情况，前者二分的是二分图两个集合之间的边，后者二分的是二分图内部的边，前者二分出来的正好是答案，后者二分出来的应该正好大于答案，所以减一之后就是答案

是不是说反了，还是说我理解错了= =

不好意思是说反了

前者减一是答案，后者是答案

这些题到底是无向图还是有向图

为啥改为if (w[i] < limit) continue;就错了捏

就是为啥在二分的时候所有大于mid的可以分到二分图中，而所有大于等于mid的分到二分图中就是错的？

因为limit这条边要在两组其中的一组内

因为mid是符合条件的最大值，也就是要在一个集合中

%%%

我龙傲天佩服！

%%%

这就是京东笔试题

太强啦，y总！

没想到这道题是这样做的。

蒟蒻求助……

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
const int N=20005,M=200005;
int n,m,tot,r=1e9,l;
int e[M],h[N],ne[M],w[M];
int v[N];
void add(int x,int y,int z){
    e[tot]=y,w[tot]=z,ne[tot]=h[x],h[x]=tot++;
}
bool dfs(int x,int col,int mid){
    v[x]=col;
    for(int i=h[x];i;i=ne[i]){
        if(w[i]<=mid) continue;
        int y=e[i];
        if(v[y]==0){
            if(!dfs(y,3-i,mid)) return false;
        }
        else if(v[y]==col) return false;
    }
    return true;
}
bool chk(int mid){
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++)
        if(v[i]==0)
            if(!dfs(i,1,mid)) return false;
    return true;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }
    while(r>l){
        int mid=(l+r)>>1;
        if(chk(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}

判断那边应该是3-col把

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c, int limit)
{
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        if (w[i] <= limit) continue;
        int j = e[i];
        if (color[j])
        {
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, limit)) return false;
    }

    return true;
}

bool check(int limit)
{
    memset(color, 0, sizeof color);

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

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &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;
    }

    printf("%d\n", l);
    return 0;
}

这里二分的结果是怎么保证一定是所给的那些边里面的啊

二分的结果如果不是某条边的权值，那就必然不是最小值，因为可以将这个结果减小到某条边的权值。

y总的思路真是太妙了囧rz

y总，想问一下 if (w[i] <= limit) continue; 的作用是什么

如果那俩个点的边小于当前的限制的话，那么这俩个点在不在二分图的一边不会影响结果，所以跳过这一条边

嗯呢，谢谢呀

这里二分的是监狱内部最大边的权值，如果边小于等于limit，那么这俩点可以在一个监狱里，只有大于limit时才不能在监狱里。所以可以把小于等于limit的点跳过。

懂了,谢谢y总

为什么注释掉这句只能过一个测试点呢？

题的关键就在于权值大于limit（二分枚举的数）的边是不是能构成二分图，注释掉就没有意义了，就相当于看全部的边能不能构成二分图了