题目：ACwing1341. 十三号星期五 题目来源：https://www.acwing.com/problem/content/1343/ 描述： 十三号星期五真的很不常见吗？ 每个月的十三号是星期五的频率是否比一周中的其他几天低？ 请编写一个程序，计算 N 年内每个月的 13 号是星期...

题目： ACwing 1343. 挤牛奶 题目来源： https://www.acwing.com/problem/content/1345/ 描述： 每天早上 5 点，三名农夫去牛场给奶牛们挤奶。 现在从 5 点开始按秒计时，第一名农夫在第 300 秒开始给牛挤奶，并在第 1000 秒停止...

Kruskal 是求最小生成树的算法，时间复杂度是$O(nlog n)$。 算法基本流程： 对所有边进行排序，按照从小到大进行排序 枚举每条边：如果两个点合并过，合并两个点，结果 += 边的长度(利用并查集) AcWing 859. Kruskal算法求最小生成树 来源: https://...

floyd 是一个求多源最短路问题，可以存在负环。时间复杂度是$O(n^3)$, 基本思路是基于动态规划的。 算法的而基本流程： 1234for k <- 1 to n: for i <- 1 to n: for j <- 1 to n: ...

Prim 是求一个最小生成树的算法。最小生成树 。 Prim算法的时间复杂度是$O(n^2)$,算法流程和Dijkstra算法非常相似。算法原理也是基于贪心实现的。 算法基本流程： 首先找到距离最近点， 初始化结果为0 把距离最近的点加入到集合中去，res += dist[t], 然后利用最...

SPFA 算法可以求单源负权边的最短路问题，时间复杂度最坏$O(nm)$， 一般是$O(n)$。SPFA求最短路的时候不能有负环，但是可以利用SPFA判断是否有负环。 算法基本流程， 流程和BFS有点类似： 首先创建一个队列，然后起点入队列。 然后每次出队列，扩展队列，更新距离最小值 最后输...

二分图： 指的是一个图可以分成两个集合，假如黑色在一个集合，白色在一个集合。 二分图的性质： 当且仅当图中不含有奇数环(图中环的边数不为奇数) 通过染色法来判断一个图是不是二分图 AcWing 860. 染色法判定二分图 来源: https://www.acwing.com/problem/c...

匈牙利算法讲的是二分图的最大匹配数。时间复杂度最坏$O(nm)$， 实际上远小于$O(nm)$。给定一个二分图，然后找到最大的匹配对数(数据不能重复使用)。 匈牙利算法也是基于贪心的一个算法。属于不到南墙终不回。算法基本流程： 为每个i找一个j，如果存在关系，并且j没有匹配，就让他两匹配 如...

算法的时间复杂度是$O(nlogm)$ 算法的基本思路的基本思路与朴树版本的Dijkstra的差别在于: 每次寻找通过遍历的方式寻找最小值$O(n)$。变为使用堆进行优化$O(log n)$ 基本思路： 首先初始化所有点为正无穷，初始起点为0 进行n - 1次循环 每次利用堆找到最小值 然后...

拓扑序的主要应用就是检测图中是否有环。如果图中没有环，能生成一个拓扑序列，一般拓扑序列不唯一。 引入两个概念， “入度” 和 “出度”: 入度: 指向节点i的边有多少条 出度: 节点i指出去的边有多少条 拓扑排序的基本思路: 首先把入度为0的点加入到队列里面去 然后依次弹出队头，扩展对头...