温州建设网站公司哪家好,游戏外包公司要不要去,建网站 京公网安,北京专业网站建设公司哪家好图的基本概念 图的种类 怎么存放图呢#xff1f; 优化 DFS
不是最快/最好的路#xff0c;但是能找到一条连通的道路。#xff08;判断两点之间是不是连通的#xff09; 蓝桥3891 import os
import sys
sys.setrecursionlimit(100000)
# 请在此输入您的代码
n, m map(int,…图的基本概念 图的种类 怎么存放图呢 优化 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实现拓扑排序
先预处理每个点的入度这个在读入边的时候处理。每次将入度为0的点入队列。每次取点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
用于求解多源最短路可以求解出任意两点的最短路
定义为点i到点j路径除去起点终点中最大编号不超过k的情况下点i到点j的最短距离。
当加入第k个点作为i到j的中间点时 利用滚动数组优化第一维度 枚举所有k 判断是否可以作为中间点可以作为中间点则优化最短路初始化:如果i,j无边则,右边则等于边权;
蓝桥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)
