专栏首页wymP1525 关押罪犯 并查集

P1525 关押罪犯 并查集

版权声明:本文为博主原创文章,遵循 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1525 关押罪犯

    题目描述 S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突...

    attack
  • 美、英、澳、加、荷5国建立联盟 打击加密货币税务犯罪

    美国和英国的税务机关领导并建立了一个旨在打击跨国金融犯罪的国际联盟,其中该联盟会针对加密货币税务犯罪。根据周二公告,新联盟“全球税务执法联合机构”(Joint ...

    C4rpeDime
  • 利用人工智能帮助警方判断罪犯危险程度

    工作在一线的警察正在对剑桥大学犯罪学家研发的人工智能系统进行试验,以利用过去的五年犯罪史统计指导警方的工作。

    思谱云汇
  • BVS智能视频分析-智慧监狱解决方案

      随着物联网、云计算、大数据技术的快速发展,在推动经济社会发展的同时,更进一步改变了人们的生活、工作方式。在监狱管理中引入新技术已成为趋势,加快智慧型监狱的建...

    倍特威视
  • 躺着就能赚钱?小心成为“背锅侠”!

    影视作品中从来不乏易容、伪装技术高超的罪犯,他们轻易变化身份,一通操作之后从容全身而退,让观众拍案叫绝。 但是被冒充的那些人,无一例外地都惹上了大麻烦。 当...

    腾讯举报中心
  • 是否拘留,算法说了算!加州全美首个废除保释金制度,用算法评估取代

    从2019年10月开始,加州将取消保释金制度,在加州被控犯罪的人将使用一种算法进行打分评估,而不再使用巨额保释金作为自由的抵押品。然后,县官员将根据算法的打分决...

    新智元
  • 网络传销头目利用“区块链”概念,发起项目短短18天吸引1.3万人投资!

    4月17日晚,一披着“区块链”外衣的特大网络传销案主犯郑某被西安警方从上海押解回西安,“4.5”特大网络传销案成功告破。 当下“区块链”概念成为当前最热门的话...

    区块链领域
  • 3000多人被骗3亿元,“虚拟货币”诈骗案曝光!

    这两年,如果不晓得“区块链”“比特币”这些流行词,都不好意思出门。一时间,各种打着“去中心化”“运用区块链技术”旗号的虚拟货币大行其道,让人难辨真假。这不,深圳...

    安恒信息
  • 泄露公司源代码算不算犯罪,会坐牢吗

    B站源代码泄露事件是今天程序猿届的热点事件,我们不应该只是作为吃瓜群众看热闹,而是要以此为戒,以避免自己永远离开这个敲码职业,小编特意找到一个类似的真实案例,分...

    后端技术探索

扫码关注云+社区

领取腾讯云代金券