最短路之Floyd：
适用领域:既可以是有向图也可以是无向图,权重可以为负，通常用来求各顶点之间的距离（多源）
缺点就是时间复杂度高，加上Python本身跑得慢....就祈祷这次题数据量不要太大
优点就是比起狄克斯特拉算法，简单地多，代码量少，容易上手
板子：
n=int(input())#这个根据题意设置，表示结点个数 edge=[[float('inf')]*n for i in range(n)] #初始化所有边权为无穷大 #根据题意更新edge[i][j] #更新的时候，如果有无向图需要edge[i][j]=edge[j][i]这样设置，否则不用 #三重循环 结束 for k in range(n): for i in range(n): for j in range(n): edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j])
最短路之狄克斯特拉：
适用领域：既可以是无向图也可以有向图，权值必须非负，求某个顶点到其他顶点的最短距离（单源）
缺点：写起来会稍微麻烦一点比起Floyd 东西比较多
优点：跑的挺快的，数据量比较大的时候也能用Python解决
板子：
n=int(input())#根据题意 n代表结点个数 edge={} #edge[i]={x:费用1，y:费用1....} 存结点之间的费用 cost=[] #cost[i]代表结点i到出发点的最短开销 s=set() #集合s用于存储处理过的结点 def find_node():#find_node函数用于寻找未被处理过的最便宜的结点 node,spend=None,float('inf') for i in range(n): if cost[i]<=spend and i not in s:# node,spend=i,cost[i] return node while node:#只要还有结点未被处理 for i in edge[node]:#遍历node的邻居 cost[i]=min(cost[i],cost[node]+edge[node][i]) s.add(node) node=find_node print(#根据你的需要输出出发点到某个结点i的费用cost[i]) #此外补充一个，如果题还要我们求最短路径上边的个数 #只需外加一个字典pre 每当更新cost[i]时,创建一个键值对 #最后通过终点逆向遍历统计次数即边数 输出即可
取模运算法则：
知识点：若x>y>0，若p=x%y,那么p一定小于y，即p∈[0,y-1]
两届连续考察了这个知识点！！重视
二分答案、Bisect模块：
题目中出现最大的某某的最小值，最小的某某的最大值，没有思路时，往往可以直接去二分答案
板子:check函数是核心
#l,r根据题意设置 红蓝区域自己定义划分 def check(x): #假设x为答案 #题目一般有有个约束条件 #如果通过某种手段使得在x的条件下存在符合约束条件的解 #那么就是可行解 while l+1!=r: mid=(l+r)//2 if check(mid): r=mid else: l=mid #取l还是r依据需要
Bisect模块：(只能用在升序数组，它源码写的时候就默认这个了QWQ)
import bisect a=[0,1,2,3,3,3,5]#一段升序数组 bisect.bisect(a,b) #返回数组a中最后一个<=b的数字的下标+1 #bisect.bisect(a,3)返回6 bisect.bisect_left(a,3) #返回数组中第一个等于3的下标 #bisect.bisect_left(a,3)返回3 #如果不存在等于3的，和bisect.bisect等效 bisect.bisect_right(a,3) #返回数组中最后一个等于3的下标+1 #bisect.bisect_right(a,3)返回6 #如果不存在等于3的，和bisect.bisect等效
这个模块通常用于查询某个序列内 属于某个区间的数的个数，>=p还是<=p?效率很高
当然也可以直接用列表解析式+len函数，但效率不高
len([i for i in a if i<=p])
#p自己设定
[贡献值法]：研究单个元素被引入后对结果的增量，实际上是把复杂的大问题转化为一个个小问题，当问题难以入手时，可以考虑这个做法
并查集:
板子
n=int(input()) #根据题意输入节点个数 #初始化 parent=[i for i in range(n)] #查找 def find_root(x): if parent[x]!=x: parent[x]=find_root(parent[x]) return parent[x] #合并 def uion(x,y): x_root,y_root=find_root(x),find_root(y) parent[x_root]=y_root
用途很广，考的频率也高哦，考试的时候多往这里想一想
最小生成树：
适用场景：对于有n个顶点的连通图，其中只有n-1条边的连通子图即最小生成树
常常这n-1条边被赋予了权值 我们需要求出最小权值和
板子：里面有并查集的内容！
n=int(input()) edge=[]#edge[i]=[a,b,c]代表i这条边连接了a,b，权值为c ans=0#权值和 edge.sort(key=lambda x:x[2])#按边权升序排序 for x in edge:#遍历所有边 a,b,c=x[0],x[1],x[2] if find_root(a)!=find_root(b) and j<=n-1:#两顶点不连通且当前边数小于n-1 ans+=x[2]#权值累加 union(a,b) j+=1 print(ans)
拓扑排序：
适用场景：有向图，检测环，有向无环图一定有拓扑序列。
板子：
graph={'a':'bc', 'b':'ef' } #graph的key表示入边,value表示被指向的点 indegrees=dict((i,0) for i in graph) #初始化入度为0 for i in graph: for j in graph[i]:#遍历i的邻居 邻居入度+1 indegrees[j]+=1 stack=[]#存入度为0的点 seq=[]#存拓扑序列 for i in indegrees: if indegrees[i]==0:#入度为0 stack.append(i)#入栈 while stack:#栈不为空 t=stack.pop(0) seq.append(t) for i in graph[t]: #邻居入度-1 indegrees[i]-=1 if indegrees[i]==0: stack.append(i) if len(seq)==len(graph): #无环 else: #有环
有关DP的，这里直接引用小蓝的笔记啦，也就是这次的榜一~写的很棒！
