// 二分图 二分+染色法 O((n+m)*30)
#include<bits/stdc++.h>
using namespace std;

const int N=20010;
vector<pair<int,int> > e[N]; //邻接表
int n,m,color[N];

bool dfs(int u,int c,int mid){
  color[u]=c;
  for(auto i:e[u]){
    int v=i.first, w=i.second;
    if(w<=mid) continue; //只保留[mid+1,1e9]的边权
    if(!color[v]){
      if(dfs(v,3-c,mid)) return 1; //有奇环,返1
    }
    else if(color[v]==c) return 1; //有奇环,返1
  }
  return 0; //无奇环,返0
}
bool check(int mid){
  memset(color,0,sizeof color);
  for(int i=1; i<=n; i++)
    if(!color[i])if(dfs(i,1,mid)) return 0; //有奇环,返0
  return 1; //无奇环,返1
}
int main(){
  scanf("%d%d",&n,&m);
  for(int a,b,c;m--;){
    scanf("%d%d%d",&a,&b,&c);
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  
  int l=-1,r=1e9+1;
  while(l+1<r){
    int mid=l+r>>1;
    if(check(mid)) r=mid; //无奇环,扩大可行区[r,1e9]
    else l=mid;
  }
  printf("%d\n",r);
}

D24 二分图判定 染色法 做法：二分答案+二分图

1.要求最大的影响力最小 -> 想到二分答案

2.将罪犯关押在两个监狱里 -> 想到二分图

具体，将所有罪犯的关系按照影响力大小从大到小排序，二分答案mid（此处的mid是数组的下标，需要用到具体值时再代入到数组中即可，具体见代码）。check函数即是判断该图是否是二分图，首先将a[mid].v大于答案的关系都连边，由于我们已经将所有关系按照影响力排序，所以直接从mid + 1到m循环，m是关系总数，将这些关系都连边即可。然后就是黑白染色判断是否是二分图，是的就返回true，反之返回false。

#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5, M=1e5+5;

struct edge{int x,y,c,pre;}a[M*2];int alen,last[N];
void ins(int x,int y,int z=0){a[++alen]={x,y,z,last[x]};last[x]=alen;}
int n,m,col[N];
bool dfs(int x,int c,int mid)//x出发遇到奇数环返回0 
{
    col[x]=c;
    for(int k=last[x];k;k=a[k].pre)
	{
        int y=a[k].y;
        if(a[k].c>mid)
		{
            if(!col[y])
			{
                if(!dfs(y,3-c,mid))return 0;
            }
            else if(col[y]==col[x])return 0;
        }
    }
    return 1;
}
bool check(int mid)
{
    memset(col,0,sizeof col);
    for(int i=1;i<=n;i++)if(!col[i])
        if(!dfs(i,1,mid))return 0;
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    alen=0;memset(last,0,sizeof(last));
    for(int i=1,x,y,c;i<=m;i++)
	{
        scanf("%d%d%d",&x,&y,&c);
        ins(x,y,c),ins(y,x,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;
}