前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P1525 关押罪犯 并查集

P1525 关押罪犯 并查集

作者头像
用户2965768
发布2019-10-22 19:58:44
3780
发布2019-10-22 19:58:44
举报
文章被收录于专栏:wym

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/101931024

题意:将一些人分成两部分,m条x与y之间有w的值,求分配后的最大的值尽量小。注意没有输出0

贪心,并查集

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/10/02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档