当前位置: 首页 > news >正文

【备战蓝桥杯】2024蓝桥杯赛前突击省一:图论模版篇

2024蓝桥杯赛前模版突击:图论篇

图论在蓝桥杯中一般考的不难,如果有图论的题,就基本是模板题,知道板子就有分了。

邻接表

本文使用方法1的方式实现邻接表

邻接表1
static int[] dist = new int[N],st = new int[N];
static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];
static int idx;static void init(){Arrays.fill(h,-1);
}
static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}
邻接表2

用来快速得到顶点的所有邻边条数

leetcode中比较常见

ArrayList<Integer>[] g = new ArrayList[N];//初始化
for(int i=0;i<n;i++)g[i] = new ArrayList<Integer>();//顶点a,b中间添加一条边
g[a].add(b);

最短路Dijkstra

单源最短路 O(mlogn)

package _00模板;
import java.util.*;public class Dijkstra {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static int[] dist = new int[N],st = new int[N];static int[] h = new int[N],e = new int[M],ne = new int[M],w = new int[M];static int idx;static int n,m;static long ans;static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}static int dijkstra(int start) {Arrays.fill(dist,INF);PriorityQueue<PII> q = new PriorityQueue<>((a,b)->a.dist-b.dist);q.add(new PII(start,0));st[start] = 0;while(q.size()>0) {PII top = q.poll();if (st[top.v]==1) continue;st[top.v] = 1;for(int i=h[top.v];i!=-1;i=ne[i]) {int j = e[i],val = w[i];if(dist[top.v]+val<dist[j]) {dist[j] = dist[top.v]+val;q.add(new PII(j,dist[j]));}}}return dist[n]!=INF?dist[n]:-1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);Arrays.fill(h,-1);n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=n;i++) {}}}
class PII{int dist;int v;public PII(int v,int dist) {// TODO Auto-generated constructor stubthis.v = v;this.dist = dist;}
}

最短路spfa

负权图的最短路O(m*n)

package _00模板;
import java.util.*;
public class Spfa {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static int[] st = new int[N],dist = new int[N];static int n,m;static long ans;static int[] h = new int[N],e = new int[M],w = new int[M],ne = new int[M];static int idx;static void add(int a,int b,int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;}static int spfa(int start) {Arrays.fill(dist,INF);Queue<Integer> q = new LinkedList<Integer>();q.add(start);st[start] = 1;dist[start] = 0;while(q.size()>0) {int top = q.poll();st[top] = 0;for(int i=h[top];i!=-1;i=ne[i]) {int j = e[i];if(dist[top]+w[i]< dist[j]) {dist[j] = dist[top]+w[i];if(st[j]==0) {st[j] = 1;q.add(j);}	}}}return dist[n]!=INF?dist[N]:-1;}}

Floyd

多源最短路O(n^3)

package _00模板;
import java.util.*;public class Floyd {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static int[][] g = new int[N][N];static int n,m;static long ans;static void floyd() {for(int k=1;k<=n;k++) {for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {g[i][j] = Math.min(g[i][j],g[i][k]+g[k][j]);}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);for(int i=1;i<=n;i++) {Arrays.fill(g[i],INF);g[i][i] = 0;}n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=m;i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();g[a][b] = c;g[b][a] = c;}floyd();}
}

最小生成树kruskal

kruskal 算法O (mlogm),Prim不需要掌握,用kruskal 就行

package _00模板;
import java.util.*;public class Kruskal {static int INF = 0x3f3f3f3f;static int N = 101000,M = 2*N;static Edge[] edges = new Edge[N];static int idx;static int n,m;static long ans;static int[] fa = new int[N];static void init() {for(int i=1;i<=n;i++) {fa[i] = i;}}static int find(int x) {if(fa[x]==x) return x;return fa[x] = find(fa[x]);}static void union(int a,int b) {fa[find(a)] = find(b);}static int kruskal() {Arrays.sort(edges,0,idx,(a,b)->(a.w-b.w));int cnt = 0,res = 0;for(int i=0;i<m;i++) {int a = edges[i].a;int b = edges[i].b;int w = edges[i].w;if(find(a)!=find(b)) {union(a,b);cnt += 1;res += w;}}return cnt==n-1?res:-1;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=m;i++) {int a = sc.nextInt();int b = sc.nextInt();int w = sc.nextInt();edges[idx++] = new Edge(a,b,w);}}
}
class Edge{int a,b,w;public Edge(int a,int b,int w) {// TODO Auto-generated constructor stubthis.a = a;this.b = b;this.w = w;}
}

拓扑排序

int[] d = new int[N];//存放入度int[] print = new int[N];//记录答案int cnt;static boolean topSort() {Queue<Integer> q = new LinkedList<Integer>();for(int i=1;i<=n;i++) {if(d[i]==0)q.add(i);}while(q.size()>0) {Integer top = q.poll();print[cnt++] = top;for(int i=h[top];i!=-1;i=ne[i]) {int j = e[i];d[j]--;if(d[j]==0) {q.add(j);}}}return n==cnt;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();for(int i=1;i<=m;i++) {int a = sc.nextInt();int b = sc.nextInt();int w = sc.nextInt();add(a,b,w);d[b] += 1;}}

相关文章:

【备战蓝桥杯】2024蓝桥杯赛前突击省一:图论模版篇

2024蓝桥杯赛前模版突击&#xff1a;图论篇 图论在蓝桥杯中一般考的不难&#xff0c;如果有图论的题&#xff0c;就基本是模板题&#xff0c;知道板子就有分了。 邻接表 本文使用方法1的方式实现邻接表 邻接表1 static int[] dist new int[N],st new int[N]; static int…...

GEE数据集——2019—2023年全球固定宽带和移动(蜂窝)网络性能(更新)

简介 全球固定宽带和移动&#xff08;蜂窝&#xff09;网络性能 全球固定宽带和移动&#xff08;蜂窝&#xff09;网络性能&#xff0c;分配给缩放级别 16 的网络 mercator 瓷砖&#xff08;赤道处约 610.8 米乘 610.8 米&#xff09;。数据以 Shapefile 格式和 Apache Parque…...

ChatGPT 写作秘籍:指导您如何利用ChatGPT撰写学术论文

ChatGPT无限次数:点击直达 ChatGPT 写作秘籍&#xff1a;指导您如何利用ChatGPT撰写学术论文 作为CSDN网站的作者&#xff0c;您可能经常面临不同类型的写作任务&#xff0c;包括学术论文的撰写。在这篇文章中&#xff0c;我们将探讨如何利用ChatGPT这一强大的文本生成工具来辅…...

【原创】springboot+mysql宠物管理系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…...

Android app如何禁止运行在模拟器中

禁止 Android 应用程序在模拟器上运行涉及到在运行时检测应用是否在模拟器上运行&#xff0c;并根据情况做出相应的处理。以下是一种方法&#xff0c;通过判断设备的某些特征来检测模拟器&#xff1a; 创建一个用于检测模拟器的方法&#xff1a; public static boolean isEmu…...

libcurl 简单实用

LibCurl是一个开源的免费的多协议数据传输开源库&#xff0c;该框架具备跨平台性&#xff0c;开源免费&#xff0c;并提供了包括HTTP、FTP、SMTP、POP3等协议的功能&#xff0c;使用libcurl可以方便地进行网络数据传输操作&#xff0c;如发送HTTP请求、下载文件、发送电子邮件等…...

华为OD技术面试-有序数组第K最小值

背景 2024-03-15华为od 二面&#xff0c;记录结题过程 有序矩阵中第 K 小的元素 - 力扣&#xff08;LeetCode&#xff09; https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/submissions/512483717/ 题目 给你一个 n x n 矩阵 matrix &#xff0c;其…...

idea如何debug看springsecurity的过滤器顺序

idea如何debug看springsecurity的过滤器顺序 先配置一个Spring启动对象,后续需要根据这个对象来获取SpringSecurity的过滤器链 设置一个输出信息&#xff0c;需要在输出信息这里打上断点&#xff0c;才方便查看过滤器链 public static void main(String[] args) {//此时不…...

【力扣】125.验证回文串

刷题&#xff0c;过了真的好有成就感&#xff01;&#xff01;&#xff01; 题解&#xff1a; 根据题目要求&#xff0c;我们需要处理一下几个问题&#xff1a; 将大写字母转变成小写对原来的字符串进行处理&#xff0c;只要字母和数字考虑只有一个和字符串为空的情况 1、将…...

Fantasy Map Creator 2

Fantasy Map Creator 2是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 Fantasy Map Creator 2是一组风格化的图像,用于在图形编辑器中创建完整的彩色地图或游戏位置,无需艺术技能或图形平板电脑。 现在,每个人都可以在…...

什么是云原生

什么是云原生 云原生的定义 aws&#xff1a; 云原生是在云计算环境中构建、部署和管理现代应用程序的软件方法。现代公司希望构建高度可伸缩、灵活和有弹性的应用程序&#xff0c;以便能够快速更新以满足客户需求。为此&#xff0c;他们使用了支持云基础设施上应用程序开发的现…...

为什么要“挺”鸿蒙?

鸿蒙到底是什么&#xff1f; 随着5G、物联网等技术的快速发展&#xff0c;智能终端设备的应用场景也越来越广泛。为了满足不同设备间的互联互通需求&#xff0c;华为在2019年推出了自主研发的操作系统——鸿蒙OS。值得关注的是&#xff0c;这也是首款国产操作系统。 要了解鸿…...

去掉el-date-picker弹窗默认回显当前月份的方法

打开日期弹窗&#xff0c;默认会显示当前月份&#xff0c;如图 会发现加了穿透&#xff1a;&#xff1a;v-deep 样式也不生效 .el-month-table .today .cell {color: pink&#xff1b;font-weight: 400;}要让 popper-class“xclass” :append-to-body“false” 这俩配合着使用…...

绝地求生:PUBG×杜卡迪联名上线!参与投稿评论赢取精美好礼

PUBG杜卡迪联名活动游戏内现已正式上线&#xff01;我们诚邀与您一起在开拓未知战场和书写新历史的过程中&#xff0c;与杜卡迪一同实现您的极速梦想&#xff01; 在本次的杜卡迪工坊中&#xff0c;更是包含了具备标志性红色在内的6种颜色供您自由选择&#xff0c;一起自由驰骋…...

10个大型语言模型(LLM)常见面试问题和答案解析

今天我们来总结以下大型语言模型面试中常问的问题 1、哪种技术有助于减轻基于提示的学习中的偏见? A.微调 Fine-tuning B.数据增强 Data augmentation C.提示校准 Prompt calibration D.梯度裁剪 Gradient clipping 答案:C 提示校准包括调整提示&#xff0c;尽量减少产生…...

rollup 插件架构-驱动设计 PluginDriver

文章目录 GraphPluginDriver生成 PluginDriver 实例和 PluginCache 缓存创建插件上下文 pluginContext初始化 pluginContext 缓存设置、方法插件中使用缓存可替换的 replace pluginContextPluginDriver 提供 asyn、first、parallel 等类型 hookgetSortedPlugins 运行时收集并存…...

netty实现mqtt(IOT)

springbootnettymqtt服务端实现 springbootnettymqtt客户端实现 MQTT协议基本讲解(结合netty) 李兴华netty视频教程中mqtt讲解 EMQX官网、mqttx客户端 IOT云平台 simple&#xff08;6&#xff09;springboot netty实现IOT云平台基本的架构&#xff08;mqtt、Rabbitmq&…...

基于STC12C5A60S2系列1T 8051单片机的液晶显示器LCD1602显示汉字的功能

基于STC12C5A60S2系列1T 8051单片机的液晶显示器LCD1602显示汉字的功能 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍LCD1602字符型液晶显示器介绍一、LCD1602字符型…...

Springboot+Redis:实现缓存 减少对数据库的压力

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏Redis实战与进阶 本专栏讲解Redis从原理到实践 …...

springboot组件的单例模式和分布式分析

springboot组件的单例模式和分布式分析 一、基本概念 在Spring Boot应用中&#xff0c;单例模式是非常常见的一种设计模式&#xff0c;它被广泛应用于Bean的生命周期管理。Spring容器默认会将所有的Component、Service、Repository和Controller注解标记的类作为单例对象进行实…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...