图论基础(python蓝桥杯)

news/2024/4/19 18:04:40/

图的基本概念

图的种类

怎么存放图呢?

优化

DFS

不是最快/最好的路,但是能找到一条连通的道路。(判断两点之间是不是连通的)

蓝桥3891

import os
import sys
sys.setrecursionlimit(100000)
# 请在此输入您的代码
n, m = map(int, input().split()) # n个点, 小明序号m
G = [[] for _ in range(n + 1)] # 邻接表,存放图。
rudu = [0] * (n + 1) # 记录每个点的入度
vis = [0] * (n + 1) # dfs的标记数组,看是否遍历过
# 二元组,分别表示每个子树数量和编号
dis = [[0, i] for i in range(n + 1)] # 排序用的二元组
for _ in range(n - 1):l, r = map(int, input().split())G[r].append(l) # r是l的父亲rudu[l] += 1
for i in range(1, n + 1):if rudu[i] == 0:root = i # 入度为0的是根节点,找到根节点,从根节点开始遍历。def dfs(u):# 同时记录每个点的子树节点数dis[u][0] = -1 # 1改成-1,以便都从小到大排序vis[u] = 1for v in G[u]:if vis[v] == 0:dfs(v)dis[u][0] += dis[v][0]dfs(root)
dis.sort()
# print(dis)
for i, (x, y) in enumerate(dis, 1): # 取出dis的排名,1的意思是索引从1开始if y == m:print(i)break

BFS

按层次分节点(几步能走的点)

不断这样取,直到终点。

蓝桥1509

import os
import sys# 请在此输入您的代码
from collections import deque
def bfs(s, t):# s起点, t终点。dis = [-1] * 100001queue = deque()# 将起点塞入队列中,打上标记。queue.append(s)dis[s] = 0# 当队列非空while len(queue) != 0:# 取出队首元素uu = queue.popleft()# 判断u是否为终点if u == t:return dis[u]# 将u相连的所有点v,只要v未标记,则打标记,入队列for v in [u - 1, u + 1, u * 2]:# 特判:越界、已标记、障碍物if 0 <= v <= 100000 and dis[v] == -1:queue.append(v)dis[v] = dis[u] + 1return -1
n, k = map(int, input().split())
print(bfs(n, k))

蓝桥3819

import os
import sys# 请在此输入您的代码
from collections import dequedef bfs(x, y, dis):queue = deque()vis = [[0] * m for i in range(n)]# 将起点入队列queue.append([x, y])dis[x][y] = 0vis[x][y] = 1while len(queue) != 0:x, y = queue.popleft()# 要求所有点,这步省略for deltax, deltay in [(1, 0), (0, 1), (-1, 0), (0, -1)]:xx, yy = x + deltax, y + deltay# 未越界,未标记,未障碍物if 0 <= xx < n and 0 < yy < m and vis[xx][yy] == 0 and g[xx][yy] != '#':queue.append([xx, yy])dis[xx][yy] = dis[x][y] + 1vis[xx][yy] = 1n, m = map(int, input().split())
INF = 1e9 # 把路堵死了,永远走不到终点。
A, B, C, D = map(int, input().split())
A, B, C, D = A - 1, B - 1, C - 1, D - 1
g = [input() for i in range(n)]
E = int(input())
dis1 = [[INF] * m for i in range(n)]
dis2 = [[INF] * m for i in range(n)]
bfs(A, B, dis1)
bfs(C, D, dis2)
res = dis1[C][D]
if res <= E:print(res)
else:# 枚举所有圣泉res = INFfor i in range(n):for j in range(m):if g[i][j] == 'V':res = min(res, dis1[i][j] + dis2[i][j])if res == INF:print("No")else:# 初始能量为E,总距离res, 后面的res-E需要花费两倍时间,因为需要等待能量恢复print((res - E) * 2 + E)

拓扑排序

拓扑排序是一种针对“有向无环图”的算法,用于解决一些有依赖关系的问题。

拓扑排序保证了处理到某个点时,其所有的入点已经处理过了。

例如下面这个图,拓扑排序可以保证:

处理点2之前,点4和点6都处理过。

处理点3之前,点2和点6都处理过。

比如学大学物理必须先学高数和线性代数。

拓扑排序的顺序并不是唯一的,就刚刚的例子,你可以先学高数再学线代,也可以先学线代再学高数。

下图是拓扑排序的几种可能性

如果有环的话找不到起点,自己想想应该就能想出来。

BFS实现拓扑排序

  1. 先预处理每个点的入度,这个在读入边的时候处理。
  2. 每次将入度为0的点入队列。
  3. 每次取点u的时候,对于从u出发的所有点v的入度-1

1此时的入度为0,相当于做了一个操作,把1->4和1->6的边给删掉了,然后发现4和6的入度又为0了。

  • 在枚举边u->v的时候,可以进行状态转移,于是可以和动态规划结合起来。
  • 这样的dp也叫DAG-DP(有向无环图上的动态规划)
  • 状态转移一般只发生在枚举所有边的时候。
模板
from collections import dequedef topo():q = deque()for i in range(1, n + 1):if ru[i] == 0:q.append(i)ans = []while len(q) != 0:u = q.popleft()ans.append(u)for v in G[u]:ru[v] -= 1if ru[v] == 0:q.append(v)if len(ans) != n:print("no topo")else:print(*ans, sep=' ')
n, m = map(int, input().split())  
G = [[] for i in range(n + 1)]
ru = [0] * (n + 1)
for _ in range(m):u, v = map(int, input().split())G[u].append(v)
topo()

蓝桥1337

import os
import sys# 请在此输入您的代码
from collections import dequedef topo():q = deque()for i in range(1, n + 1):if ru[i] == 0:q.append(i)while len(q) != 0:# 取出队首元素u = q.popleft()# 对于和u相邻的每个点vfor v in G[u]:# 从u走到v,说明dp[v]可以从dp[u] + 1转移过来dp[v] = max(dp[v], dp[u] + 1)ru[v] -= 1if ru[v] == 0:q.append(v)# dp[i] 表示走到i的最长路,也就是最大值。      
n, m = map(int, input().split())
dp = [0] * (n + 1)  
G = [[] for i in range(n + 1)]
ru = [0] * (n + 1)
for _ in range(m):u, v = map(int, input().split())G[u].append(v)
topo()
print(max(dp))

蓝桥3351

import os
import sys
from queue import PriorityQueue
# 请在此输入您的代码def topo():q = PriorityQueue()for i in range(1, n + 1):if ru[i] == 0:q.put(i)ans = []while not q.empty():u = q.get()ans.append(u)for v in G[u]:ru[v] -= 1if ru[v] == 0:q.put(v)if len(ans) != n:print(-1)else:print(*ans, sep=' ')
n, m = map(int, input().split())
G = [[] for i in range(n + 1)]
ru = [0] * (n + 1)
for _ in range(m):u, v = map(int, input().split())G[u].append(v)ru[v] += 1
topo()

Floyd

用于求解多源最短路,可以求解出任意两点的最短路

定义dp[k][i][j]为点i到点j路径(除去起点终点)中最大编号不超过k的情况下,点i到点j的最短距离。

当加入第k个点作为i到j的中间点时

dp[k][i][j]= min(dp[k - 1][i][j],dp[k - 1][i][k]+ dp[k - 1][k][j])

利用滚动数组优化第一维度

dp[i][j]= min(dp[i][j],dp[i][k]+ dp[k][j])

枚举所有k ,判断是否可以作为中间点,可以作为中间点则优化最短路初始化:如果<i,j>无边,则dp[i][j] = INF,右边则等于边权;
dp[i][i]= 0

蓝桥1121

import os
import sys# 请在此输入您的代码
n, m, q = map(int, input().split())
INF = 1e18 
dp = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(1, n + 1):dp[i][i] = 0
for _ in range(m):u, v, w = map(int, input().split())dp[u][v] = dp[v][u] = min(dp[u][v], w)for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
for _ in range(q):u, v = map(int, input().split())if dp[u][v] == INF:print(-1)else:print(dp[u][v])

蓝桥8336

import os
import sys# 请在此输入您的代码
n, m = map(int, input().split())
a, p, s = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
INF = 1e9
f = [[INF] * (n + 1) for i in range(n + 1)]
g = [[0] *(n + 1) for i in range(n + 1)]for i in range(1, n + 1):a[i], p[i], s[i] = map(int, input().split())
for i in range(1, m + 1):u, v, w = map(int, input().split())f[u][v] = f[v][u] = min(f[u][v], w)
for i in range(1, n + 1):f[i][i] = 0
for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):f[i][j] = min(f[i][j], f[i][k] + f[k][j])
for i in range(1, n + 1):for j in range(1, n + 1):g[i][j] = s[j] - p[i] - f[i][j]
ans = 0
for i in range(1, n + 1):now_ans = 0for j in range(1, n + 1):now_ans = max(now_ans, a[i] * g[i][j])ans += now_ans
print(ans)


http://www.ppmy.cn/news/1405476.html

相关文章

基于单片机按键控制看门狗仿真设计

**单片机设计介绍&#xff0c;基于单片机按键控制看门狗仿真设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机按键控制看门狗仿真设计概要主要涉及利用单片机上的按键来控制看门狗的功能&#xff0c;从而实现系统故障的及时检…

LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】

LeetCode-146. LRU 缓存【设计 哈希表 链表 双向链表】 题目描述&#xff1a;解题思路一&#xff1a;双向链表&#xff0c;函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。一张图&#xff1a;知识点__slots__ 解题思路二&#xff1a;0解题思路三&#xff1a;0 题目描述&am…

Maven入门指南:构建与管理Java项目的利器

引言 在Java开发领域&#xff0c;项目构建和管理是一个至关重要的环节。随着项目规模和复杂度的不断增加&#xff0c;有效地管理项目的依赖、构建过程以及部署流程变得尤为关键。在这样的背景下&#xff0c;Apache Maven作为一款优秀的项目管理工具应运而生&#xff0c;成为了…

STC8H8K64U 学习笔记 - 基础代码

STC8H8K64U 学习笔记 - 基础代码 环境说明引脚说明 基础代码电动马达蜂鸣器小蓝灯LED 灯走马灯来回灯流水灯流水逐灭灯相遇灯 独立按键 串口串口接收查询按键反馈 环境说明 该内容仅针对我自己学习的开发板做的笔记&#xff0c;在实际开发中需要针对目标电路板的原理图进行针对…

使用浏览器打开本地的exe程序并传递参数

使用浏览器打开本地的exe程序并传递参数 html文件 其中OpenProgramByBroswer: 为协议名称&#xff0c;名称后面要跟上英文的冒号。 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport&…

【讲解下Gitea】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

基于Springboot + MySQL + Vue 大学新生宿舍管理系统 (含源码)

目录 &#x1f4da; 前言 &#x1f4d1;摘要 &#x1f4d1;操作流程 &#x1f4da; 系统架构设计 &#x1f4da; 数据库设计 &#x1f4ac; 管理员信息属性 &#x1f4ac; 学生信息实体属性 &#x1f4ac; 宿舍安排信息实体属性 &#x1f4ac; 卫生检查信息实体属性 &…

使用vuepress搭建个人的博客(一):基础构建

前言 vuepress是一个构建静态资源网站的库 地址:VuePress 一般来说,这个框架非常适合构建个人技术博客,你只需要把自己写好的markdown文档准备好,完成对应的配置就可以了 搭建 初始化和引入 创建文件夹press-blog npm初始化 npm init 引入包 npm install -D vuepress…

docker安装rabbitMQ,并且创建账号

# 创建docker容器启动,挂到后台运行 docker run -d --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.13-management # 打开防火墙 sudo firewall-cmd --zonepublic --add-port5672/tcp --permanent sudo firewall-cmd --zonepublic --add-port15672/tcp --permanent s…

P2089 烤鸡——Python解答

题目背景 猪猪 Hanke 得到了一只鸡。 题目描述 猪猪 Hanke 特别喜欢吃烤鸡&#xff08;本是同畜牲&#xff0c;相煎何太急&#xff01;&#xff09;Hanke 吃鸡很特别&#xff0c;为什么特别呢&#xff1f;因为他有 1010 种配料&#xff08;芥末、孜然等&#xff09;&#xf…

【电路笔记】-逻辑与门

逻辑与门 文章目录 逻辑与门1、概述2、2 输入晶体管与门3、数字与门类型4、7408 四路 2 输入与门逻辑与门是一种数字逻辑电路,仅当其所有输入均为高电平时,其输出才会变为高电平至逻辑电平 1。 1、概述 数字逻辑与门的输出状态仅在其任何输入处于逻辑电平“0”时再次返回“低…

知识图谱在五大智能领域的应用

知识图谱是一种新型的图数据模型&#xff0c;其核心思想是&#xff1a;通过实体和关系来描述一个数据集&#xff0c;而不是像传统关系数据库那样&#xff0c;将数据存储在不同的数据库中&#xff0c;而是可以让用户对数据进行检索和分析。知识图谱通过三元组&#xff08;实体、…

Linux提权!!!

上一篇文章讲了Windows的提权&#xff0c;那么这篇文章就来讲一下Linux的提权 1.SUID提权 suid权限 作用&#xff1a;让普通用户临时拥有该文件的属主的执行权限&#xff0c;suid权限只能应用在二进制可执行文件&#xff08;命令&#xff09;上&#xff0c;而且suid权限只能设置…

《QT实用小工具·三》偏3D风格的异型窗体

1、概述 源码放在文章末尾 可以在窗体中点击鼠标左键进行图片切换&#xff0c;项目提供了一些图片素材&#xff0c;整体风格偏向于3D类型&#xff0c;也可以根据需求自己放置不同的图片。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; 头文件部分&#xff…

linux设置Nacos自启动

前提&#xff1a;已经安装好nacos应用 可参考&#xff1a;Nacos单机版安装-CSDN博客 1. 创建nacos.service 1.1 在 /lib/systemd/system 目录底下&#xff0c;新建nacos.service文件 [Unit] Descriptionnacos Afternetwork.target[Service]Typeforking# 单机启动方式&#…

I2C总线与AT24C02

目录 I2C总线 I2C总线介绍 I2C电路规范 I2C时序结构 起始与终止 代码理解 发送字节 代码理解 接收字节 代码理解 数据应答 代码理解 I2C的数据据帧 发送数据帧 接收数据帧 发送接收数据帧 AT24C02芯片 AT24C02介绍 引脚及应用电路 内部结构图 AT24C02数据…

对【AI技术创业】有哪些机会进行分析和引导

文章目录 方向一&#xff1a;行业解决方案,以下是一些常见的行业解决方案&#xff1a;方向二&#xff1a;智能产品和服务,以下是一些智能产品和服务的示例&#xff1a;方向三&#xff1a;教育和培训 1.智能客户服务&#xff1a; 利用自然语言处理&#xff08;NLP&#xff09;和…

【Algorithms 4】算法(第4版)学习笔记 23 - 5.4 正则表达式

文章目录 前言参考目录学习笔记1&#xff1a;正则表达式1.1&#xff1a;表示1.2&#xff1a;快捷表示2&#xff1a;正则表达式与非确定有限状态自动机 REs and NFAs2.1&#xff1a;二元性2.2&#xff1a;模式匹配实现2.3&#xff1a;非确定有限状态自动机 Nondeterministic fin…

go: go.mod file not found in current directory or any parent directory.如何解决?

这个错误表明你正在执行 go get 命令&#xff0c;但是当前目录或任何父目录中都找不到 go.mod 文件。这可能是因为你的项目还没有使用 Go Modules 进行管理。 要解决这个问题&#xff0c;有几种方法&#xff1a; go mod init <module-name> 其中 <module-name>…

Quill文档(五):Delta格式

富文本编辑器缺乏一种表达其自身内容的规范。直到最近&#xff0c;大多数富文本编辑器甚至不知道它们自己的编辑区域中有什么内容。这些编辑器只是传递用户的HTML&#xff0c;以及解析和解释这些HTML的负担。在任何给定的时间&#xff0c;这种解释都会与主要浏览器供应商的解释…