版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41603898/article/details/101931024
题意:将一些人分成两部分,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;
}