这道题可怜蒟蒻我只写对一个样例/(ㄒoㄒ)/~~

不过好在学废了😂
方法有两类,一类用并查集,第二类用二分图和二分(洛谷题解区是最好的老师[谄媚])
那么我就可以知道,至少有两种方法[显摆]

并查集

方法一:单独开一个数组来装当前单独样例的敌人(是在降序排序之后从头开始的,这些一定要是敌人,一定要在不同监狱)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
  int a, b, c;
}com[N];
int p[N],rb[N];
int n, m;
int find(int x) 
{
  if(p[x]!=x) p[x] = find(p[x]);
  return p[x];
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)p[i] = i;
  for (int i = 1; i <= m; i++)
    cin >> com[i].a >> com[i].b >> com[i].c;
  sort(com + 1, com + 1 + m, [](node a, node b)
    {return a.c > b.c;}
  );
  for (int i = 1; i <= m + 1; i++) {//com[i].a,com[i].b,com[i].c
    if(find(com[i].a) == find(com[i].b)) {
      cout << com[i].c << endl;
      return 0;
    } else {
      if(!rb[com[i].a]) rb[com[i].a] = com[i].b;
      else p[find(rb[com[i].a])] = find(com[i].b);
      if(!rb[com[i].b]) rb[com[i].b] = com[i].a;
      else p[find(rb[com[i].b])] = find(com[i].a);
    }
  }
  return 0;
}

方法二:成立假想敌,对于i,那么它的敌人就是i+n
对于样例(简化了)

3 2
1 2 5
1 3 6

1的敌人是1+3为4,那么2和4就在同一组,同理1和2+3为5,就在同一组
最终得到两组(也只让得到两组):{1,5,6}和{2,3,4},简而言之就是通过共同的假想敌来达到在同一组的目的

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node{
  int x, y, z;
} a[N];
int m, n, f[N];
inline int find(int x)
{
  if(f[x] != x) f[x] = find(f[x]);
  return f[x];
}
int main()
{
  cin >> n >> m;
  if(m<=1){
    cout << 0 << endl;
    return 0;
  } 
  for (int i = 1; i <= 2*n; i++) f[i] = i;
  for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].z;
  sort(a + 1, a + 1 + m, [](node a, node b){ return a.z > b.z; });
  for (int i = 1; i <= m; i++) {
    int x = a[i].x, y = a[i].y;
    if(find(x)==find(y)) {
      cout << a[i].z << endl;
      return 0;
    }
    f[find(x+n)] = find(y);
    f[find(y+n)] = find(x);
  }
  return 0;
}

二分+二分图

二分答案,将得到的预测试答案为分界,那么比它更大的一定在不同的监狱中,一定可以构成二分图
dfs的作用是画图,不用返回其他bool变量,递归画图,然后测试画图的结果,有没有重叠
初始化默认color数组全是0,不用考虑的部分是0,要考虑的部分是0和1的交替(0开始),即便没有st数组去判断这个带你是否走过,凭借!color布尔判断也是可以及时阻断的,不必担心时间功耗过大

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node{
  int x, y, z;
} a[N];
int m, n,color[N],flag;
vector<int> e[N];
inline void dfs(int x,int y)
{
  color[x] = y;
  for (int i = 0; i < e[x].size(); i++){
    int v = e[x][i];
    if(!color[v]) {
      dfs(v, y ^ 1);
    }
    else if(color[v] == y) {
      flag = 0;
      return;
    }
  }
  return;
}
inline bool check(int p)
{
  for (int i = 1; i <= n; i++) e[i].clear();
  flag = 1;
  memset(color, 0, sizeof(color));
  for (int i = p + 1; i <= m; i++){
    e[a[i].x].push_back(a[i].y);
    e[a[i].y].push_back(a[i].x);
  }
  for (int i = 1; i <= n; i++) {
    if(!color[i]) {
      dfs(i, 0);
      if(!flag) return 0;
    }
  }
  return 1;
}
int main()
{
  cin >> n >> m;
  for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].z;
  sort(a + 1, a + 1 + m, [](node a, node b){ return a.z < b.z; });
  int l = 0, r = m + 1, mid;
  while(l<r) {
    mid = (l + r) >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
  }
  if(m==1) cout << "0\n";
  else cout << a[l].z << endl;
  return 0;
}