备战蓝桥杯---搜索(完结篇)

再看一道不完全是搜索的题:

解法1:贪心+并查集:

把冲突事件从大到小排,判断是否两个在同一集合,在的话就返回,不在的话就合并。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c;
struct node{int x,y,qi;
}a1[100010];
int fa[50000];
bool cmp(node a,node b){return a.qi>b.qi;
}
int find(int x){if(fa[x]==x) return x;else return fa[x]=find(fa[x]);
}
void merge(int x,int y){fa[find(x)]=find(y);
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d%d",&a1[i].x,&a1[i].y,&a1[i].qi);}for(int i=1;i<=2*n+1;i++){fa[i]=i;}sort(a1+1,a1+1+m,cmp);int f=0;for(int i=1;i<=m;i++){int xx=a1[i].x;int yy=a1[i].y;if(find(xx)==find(yy)){cout<<a1[i].qi;f=1;break;}else{merge(xx,n+yy);merge(xx+n,yy);}}if(f==0) cout<<0;
}

解法2:二分+DFS

显然这是一个0/1单调函数,我们可以进行二分。那我们二分出值如何判断是否可行?

我们可以把有怨气值的连边,对每个联通块种的大于二分值的DFS,先把自己-》1,与他相连的赋为0,以此类推,看是否有两个0/1值相同并相连的节点。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a,b,c,qi;
struct node{int aa,qi1;
};
vector<node> tu[20005];
int vis[20005];
int heibai[20005];
int dfs(int x,int fa,int mid){int f=0;vis[x]=1;heibai[x]=1-heibai[fa];for(int i=0;i<tu[x].size();i++){if(tu[x][i].qi1<=mid) continue;if(tu[x][i].aa==fa) continue;if(vis[tu[x][i].aa]==1&&heibai[tu[x][i].aa]==heibai[x]){f=1;continue;}if(vis[tu[x][i].aa]==1) continue;if(dfs(tu[x][i].aa,x,mid)==1) f=1;}
return f;
}
int check(int mid){memset(vis,0,sizeof(vis));memset(heibai,0,sizeof(heibai));int f=1;for(int i=1;i<=n;i++){if(vis[i]==1) continue;if(dfs(i,0,mid)==1){f=0;break;}}return f;
}
signed main(){cin>>n>>m;for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);tu[a].push_back({b,c});tu[b].push_back({a,c});qi=max(qi,c);}int i=0,j=qi;while(i<j){int mid=(i+j)/2;if(check(mid)==1) j=mid;else i=mid+1;}cout<<i;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/258046.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LabVIEW荧光显微镜下微管运动仿真系统开发

LabVIEW荧光显微镜下微管运动仿真系统开发 在生物医学研究中&#xff0c;对微管运动的观察和分析至关重要。介绍了一个基于LabVIEW的仿真系统&#xff0c;模拟荧光显微镜下微管的运动过程。该系统提供了一个高效、可靠的工具&#xff0c;用于研究微管与运动蛋白&#xff08;如…

网络安全的今年:量子、生成人工智能以及 LLM 和密码

尽管世界总是难以预测&#xff0c;但网络安全的几个强劲趋势表明未来几个月的发展充满希望和令人担忧。有一点是肯定的&#xff1a;2024 年将是非常重要且有趣的一年。 近年来&#xff0c;人工智能&#xff08;AI&#xff09;以令人难以置信的速度发展&#xff0c;其在网络安全…

Spring Boot 笔记 019 创建接口_文件上传

1.1 创建阿里OSS bucket OSS Java SDK 兼容性和示例代码_对象存储(OSS)-阿里云帮助中心 (aliyun.com) 1.2 编写工具类 package com.geji.utils;import com.aliyun.oss.ClientException; import com.aliyun.oss.OSS; import com.aliyun.oss.OSSClientBuilder; import com.aliyun…

深度学习基础之《深度学习介绍》

一、深度学习与机器学习的区别 1、特征提取方面 机器学习&#xff1a;人工特征提取 分类算法 深度学习&#xff1a;没有人工特征提取&#xff0c;直接将特征值传进去 &#xff08;1&#xff09;机器学习的特征工程步骤是要靠手工完成的&#xff0c;而且需要大量领域专业知识…

Android之Android.bp文件格式语法(一百八十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

LabVIEW高效电磁阀性能测试

LabVIEW高效电磁阀性能测试 在核电站的安全运营中&#xff0c;电磁阀作为关键组件&#xff0c;其性能的可靠性至关重要。设计一套基于LabVIEW的电磁阀测试平台&#xff0c;既能精准测试电磁阀的多项性能指标&#xff0c;又能提高检修效率与准确性&#xff0c;进而保障核电站的…

关于内存相关的梳理

1 关键字 总结 &#xff08;lowmemory&#xff0c;anr in&#xff09; 2 知识储备 虚拟机原理 垃圾回收算法 又包含标记 和清除两种算法 标记&#xff1a;程序计数器-已过时&#xff0c;可达性分析 具体可见 http://help.eclipse.org/luna/index.jsp?topic%2Forg.ec…

消息中间件:Puslar、Kafka、RabbigMQ、ActiveMQ

消息队列 消息队列&#xff1a;它主要用来暂存生产者生产的消息&#xff0c;供后续其他消费者来消费。 它的功能主要有两个&#xff1a; 暂存&#xff08;存储&#xff09;队列&#xff08;有序&#xff1a;先进先出 从目前互联网应用中使用消息队列的场景来看&#xff0c;…

SpringCloud第一天

1.认识微服务 随着互联网行业的发展&#xff0c;对服务的要求也越来越高&#xff0c;服务架构也从单体架构逐渐演变为现在流行的微服务架构。这些架构之间有怎样的差别呢&#xff1f; 1.1.单体架构 单体架构&#xff1a;将业务的所有功能集中在一个项目中开发&#xff0c;打…

四、案例 - Oracle数据迁移至MySQL

Oracle数据迁移至MySQL 一、生成测试数据表和数据1.在Oracle创建数据表和数据2.在MySQL创建数据表 二、生成模板文件1.模板文件内容2.模板文件参数详解2.1 全局设置2.2 数据读取&#xff08;Reader&#xff09;2.3 数据写入&#xff08;Writer&#xff09;2.4 性能设置 三、案例…

qt “美颜”

要想成为一名优秀的qt工程师 学会使用qss编程也是重要的 不可获缺的一部分 qss 简介和优势 QSS&#xff08;Qt Style Sheets&#xff09;是一种用于定义Qt应用程序界面外观和样式的样式表语言。它类似于CSS&#xff08;层叠样式表&#xff09;&#xff0c;但针对Qt框架进行了定…

高仿原神官网UI 纯html源码

高仿原神官网UI源码介绍 如果您希望打造一个与原神官方网站相似的外观和用户体验&#xff0c;但又不想使用复杂的框架或模板&#xff0c;那么我们的高仿原神官网UI源码将是一个完美的选择。它采用纯HTML5构建&#xff0c;无需任何额外的CSS或JavaScript库支持&#xff0c;即可…

(三十五)大数据实战——Superset可视化平台搭建

前言 本节内容是关于Apache Superset可视化平台的搭建&#xff0c;Apache Superset是一个现代的数据探索和可视化平台 。它功能强大且十分易用&#xff0c;可对接各种数据源&#xff0c;包括很多现代的大数据分析引擎&#xff0c;拥有丰富的图表展示形式&#xff0c;并且支持自…

Flutter Android开发 梳理Google Material Design颜色体系

前言 做安卓开发&#xff08;Kotlin语言&#xff09;&#xff0c;Flutter开发的人员应该都听说过谷歌一直推崇的Material Design&#xff0c;而Material Design Color是其推崇的颜色体系&#xff0c;具体来说&#xff0c;Material Design Color是一套旨在帮助设计师和开发者创…

计算机网络——12DNS

DNS DNS的必要性 IP地址标识主机、路由器但IP地址不好记忆&#xff0c;不便于人类用使用&#xff08;没有意义&#xff09;人类一般倾向于使用一些有意义的字符串来标识Internet上的设备存在着“字符串”——IP地址的转换的必要性人类用户提供要访问机器的“字符串”名称由DN…

基于微信小程序的校园失物招领小程序

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

【光学】学习记录1-几何光学的近轴理论

课程来源&#xff1a;b站资源-光学-中科大-崔宏滨老师&#xff08;感谢&#xff09;&#xff0c;本系列仅为自学笔记 【光学 中科大 崔宏滨老师 1080p高清修复&#xff08;全集&#xff09;】https://www.bilibili.com/video/BV1NG4y1C7T9?p2&vd_source7ba37b2cff2a1b783…

Python一些可能用的到的函数系列124 GlobalFunc

说明 GlobalFunc是算网的下一代核心数据处理基础。 算网是一个分布式网络&#xff0c;为了能够实现真的分布式计算&#xff08;加快大规模任务执行效率&#xff09;&#xff0c;以及能够在很长的时间内维护不同版本的计算方法&#xff0c;需要这样一个对象/服务来支撑。Globa…

【闲谈】开源软件的崛起与影响

随着信息技术的快速发展&#xff0c;开源软件已经成为软件开发的趋势&#xff0c;并产生了深远的影响。开源软件的低成本、可协作性和透明度等特点&#xff0c;使得越来越多的企业和个人选择使用开源软件&#xff0c;促进了软件行业的繁荣。然而&#xff0c;在使用开源软件的过…

内网穿透工具

1. nps-npc 1.1 简介 nps是一款轻量级、高性能、功能强大的内网穿透代理服务器。目前支持tcp、udp流量转发&#xff0c;可支持任何tcp、udp上层协议&#xff08;访问内网网站、本地支付接口调试、ssh访问、远程桌面&#xff0c;内网dns解析等等……&#xff09;&#xff0c…