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

量子力学的抽象地位与c语言等价

多种量子/粒子的各种表象&#xff0c;就像 cpu 的微架构指令集&#xff0c;量子力学的状态矢量表示和密度矩阵表示就像c语言。 中间从状态矢量到具体粒子的具体表象的转换&#xff0c;就像是一个编译器的工作。量子力学表象与编译器架构的深刻类比这个类比非常精妙且深刻&#…...

从零部署Jetson Xavier NX:Ubuntu 20.04系统烧录、CUDA环境配置与深度学习框架实战指南

1. 开箱与硬件准备 第一次拿到Jetson Xavier NX开发板时&#xff0c;我差点被它小巧的尺寸骗了——这个巴掌大的板子居然藏着384个CUDA核心和48个Tensor核心。我入手的是带128GB SSD的EMMC版本&#xff0c;实测下来这套配置跑YOLOv5这类中等规模的模型完全够用。开箱清单里除了…...

手机号查询QQ技术解析与实战指南

手机号查询QQ技术解析与实战指南 【免费下载链接】phone2qq 项目地址: https://gitcode.com/gh_mirrors/ph/phone2qq 问题&#xff1a;数字化时代的身份关联困境 在现代社会&#xff0c;手机号与QQ号作为重要的数字身份标识&#xff0c;其关联查询需求日益凸显。当用户…...

当Task.Run遇上CancellationToken:C#异步编程中的‘紧急停止‘按钮设计

当Task.Run遇上CancellationToken&#xff1a;C#异步编程中的紧急停止按钮设计 在现代软件开发中&#xff0c;异步编程已成为提升应用响应能力和资源利用率的关键技术。C#作为一门成熟的编程语言&#xff0c;提供了强大的异步编程模型&#xff0c;其中Task.Run和CancellationTo…...

ANPC-VSG(虚拟同步机)控制,基于有源中点钳位三电平的VSG构网型逆变器控制,采用LCL...

ANPC-VSG&#xff08;虚拟同步机&#xff09;控制&#xff0c;基于有源中点钳位三电平的VSG构网型逆变器控制&#xff0c;采用LCL型滤波器&#xff0c;电压电流双闭环控制。 1.VSG控制 2.中点电位平衡控制 3.电压电流双闭环控制 4.提供参考文献以及VSG原理和下垂系数计算方法 支…...

技术探索:硬件信息伪装的内核级实现方案

技术探索&#xff1a;硬件信息伪装的内核级实现方案 【免费下载链接】EASY-HWID-SPOOFER 基于内核模式的硬件信息欺骗工具 项目地址: https://gitcode.com/gh_mirrors/ea/EASY-HWID-SPOOFER 如何通过驱动级操作实现系统硬件标识的深度修改&#xff1f; 技术解析&#x…...

图片木马检测与防御:如何用PHP代码识别恶意图片上传(2024最新版)

图片木马检测与防御&#xff1a;2024年PHP实战指南 在数字化浪潮中&#xff0c;图片上传功能已成为网站标配&#xff0c;但这也为攻击者提供了可乘之机。去年某电商平台因图片木马导致百万用户数据泄露的事件&#xff0c;再次敲响了安全警钟。本文将深入剖析如何用PHP构建坚不可…...

避开SDR通信的‘坑’:我在用Pluto做16QAM传输时遇到的相位偏移和同步问题

避开SDR通信的‘坑’&#xff1a;我在用Pluto做16QAM传输时遇到的相位偏移和同步问题 第一次用Pluto SDR搭建16QAM通信链路时&#xff0c;我盯着屏幕上扭曲的星座图发呆了半小时——理论上完美的16个星点&#xff0c;在实际接收时却像被无形的手揉成了一团毛线。这种挫败感想必…...

【STM32F407VET6开发】第二章 Keil 5环境配置与Pack Installer实战指南

1. Keil 5环境配置全流程解析 第一次接触STM32开发的朋友&#xff0c;安装完Keil 5后往往会遇到各种环境配置问题。我当年用STM32F407VET6做第一个项目时&#xff0c;光是让开发环境跑起来就折腾了两天。现在回头看&#xff0c;其实只要掌握几个关键步骤&#xff0c;整个过程可…...

csvlens作为库使用教程:在Rust项目中集成CSV查看功能

csvlens作为库使用教程&#xff1a;在Rust项目中集成CSV查看功能 【免费下载链接】csvlens Command line csv viewer 项目地址: https://gitcode.com/gh_mirrors/cs/csvlens 想要在你的Rust应用中添加一个功能强大、交互式的CSV数据查看器吗&#xff1f;csvlens不仅是一…...