当前位置: 首页 > 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注解标记的类作为单例对象进行实…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...