题意：将一些人分成两部分，m条x与y之间有w的值，求分配后的最大的值尽量小。注意没有输出0
贪心，并查集
#include <bits/stdc++.h> using namespace std; const int maxn = 20005; struct N{ int x,y,z; }no[100005]; bool cmp(N c,N d){ return c.z>d.z; } int n,m; int fa[maxn],ar[maxn]; inline int getf(int x){ if(fa[x]==x)return fa[x]; else { fa[x] = getf(fa[x]); return fa[x]; } } inline int check(int x,int y){ int t1 = getf(x); int t2 = getf(y); if(t1==t2)return 1; else return 0; } inline void add(int x,int y){ int t1 = getf(x); int t2 = getf(y); fa[t1] = t2; } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d %d %d",&no[i].x,&no[i].y,&no[i].z); } sort(no+1,no+1+m,cmp); for(int i=1;i<=n;i++)fa[i] = i; for(int i=1;i<=m;i++){ if(check(no[i].x,no[i].y)){printf("%d\n",no[i].z);return 0; }else{ if(!ar[no[i].x])ar[no[i].x] = no[i].y; else add(ar[no[i].x],no[i].y);//敌人的敌人进入一个监狱 if(!ar[no[i].y])ar[no[i].y] = no[i].x; else add(ar[no[i].y],no[i].x); } } printf("0\n"); return 0; }
