题目链接：https://www.luogu.com.cn/problem/list?keyword=1525&page=1
题目给出一些点对之间的权值，要求把点对分到两个集合之中，使得两个集合中的最大边的值最小。我们考虑到将点对分成两个集合可以用并查集的分集合方法得到，1-n表示的是一个集合，n+1-2*n表示的是另一个集合，因为我们不会人为的将x和x+n合并，所以x+n所在集合与x所在的集合一定是相互排斥的，也就是说x+n集合是所有不和x一个集合的结点构成的集合。本题只要贪心地扫一遍最大边就可以。将边排序之后我们逐个选择最大边，分为两种情况。
1、如果最大边的两个结点不在同一个集合中，我们就把他分到两个集合中，因为如果合并到一个集合之中就已经结束了，但是接下来可能会有更小的边满足条件，所以分在两个集合之中。
2、如果最大边的两个结点已经在同一个集合中，这条边就是答案，因为他们已经是某个集合中的最大边，而且两个集合中已经没有任何一条边比它大。此时就实现了最大边的最小化。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x3f3f3f3f 20 const int maxn=1e6+10; 21 int n,m,t; 22 inline int read(){ 23 int ans=0,w=1; 24 char ch=getchar(); 25 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 26 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 27 return ans*w; 28 } 29 struct node{ 30 int u,v,w; 31 }p[maxn]; 32 int f[maxn]; 33 void init() 34 { 35 f(i,1,2*n)f[i]=i; 36 } 37 int find(int x ) 38 { 39 return x==f[x]?x:f[x]=find(f[x]); 40 } 41 bool cmp(node& a,node& b) 42 { 43 return a.w>b.w; 44 } 45 int main() 46 { 47 //freopen("input.txt","r",stdin); 48 //freopen("output.txt","w",stdout); 49 std::ios::sync_with_stdio(false); 50 n=read(),m=read(); 51 init(); 52 f(i,1,m) 53 { 54 p[i].u=read(),p[i].v=read(),p[i].w=read(); 55 } 56 sort(p+1,p+m+1,cmp); 57 f(i,1,m) 58 { 59 int x=find(p[i].u); 60 int y=find(p[i].v); 61 if(x==y) 62 { 63 pf("%d",p[i].w); 64 return 0; 65 } 66 else 67 { 68 f[x]=find(n+p[i].v);//注意传的是结点 69 f[y]=find(n+p[i].u); 70 } 71 } 72 pf("0"); 73 return 0; 74 }