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

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...