题目描述
小美想：整个暑假不能全部用来锻炼，也应该收集一些回忆。
整个暑假的回忆将被小美分为两部分：好回忆和坏回忆。
但是并不是所有回忆都可以相安无事的，所以小美也不会随意划分这些回忆的种类。
一个回忆可能会跟其它的一些回忆产生“冲突”，这个“冲突”有一个值 c ，而小美会用波动值来描述整个暑假的美好程度。
只要会产生冲突的两个回忆同时被划分到好回忆或者坏回忆中，小美的波动值就可能发生变化。
具体来说，小美的波动值取决于在最后的划分结果中，同一回忆（好回忆或者坏回忆）种类下最大的那个冲突值。
小美想要自己的暑假尽可能的美好，所以她想请你帮她来划分回忆，使得最后的波动值最小。
输入描述:
输出描述:
输出一个整数，表示最小的波动值 。
示例1
输入
复制4 6 2 3 8 1 3 6 2 3 1 4 3 2 1 2 4 1 4 10
4 6 2 3 8 1 3 6 2 3 1 4 3 2 1 2 4 1 4 10
输出
复制4
4
做法
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct ty{int a,b,c;
}e[100010];
int fa[50010];
int getfa(int x){if(x==fa[x]) return x;return fa[x]=getfa(fa[x]);
}
void setfa(int x,int y){fa[getfa(x)]=getfa(y);
}
int isleft(int x){for(int i=1;i<=n+n;i++) fa[i]=i;for(int i=1;i<=m;i++){if(e[i].c>x){//e[i].a和e[i].b都不能和getfa(e[i].a)在一个集合里，一共只有两个集合，所以他两在一个集合//但是现在e[i].c>x，e[i].a和e[i].b也不能在一个集合里，因此x不满足if(getfa(e[i].a)==getfa(e[i].b)) return 1;setfa(e[i].a,e[i].b+n);//以e[i].b+n为根的集合都是不能和b在一个集合的点setfa(e[i].b,e[i].a+n);//以e[i].a+n为根的集合都是不能和a在一个集合的点}}return 0;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);}int l=-1,r=1e6;while(l+1<r){int mid=l+(r-l)/2;if(isleft(mid)) l=mid;else r=mid;}cout<<r;
}
