【笔记/模板】Floyd算法以及扩展应用
Floyd 算法
原理
Floyd 算法用来求出任意两个节点之间的最短路。
优点：代码少，思维简单，适用于除了负环以外的任何图。
缺点：时间复杂度为 O(n3)O(n ^ 3)O(n3)，空间复杂度为 O(n2)O(n ^ 2)O(n2)。
而 Floyd 的核心原理是用动态规划实现的，定义一个二维数组 fi,jf_{i, j}fi,j，遍历图上的所有点 kkk，可以得到如下公式：
f[i][j]=min(f[i][j],f[i][k]+f[k][j])f[i][j] = min(f[i][j], f[i][k] + f[k][j])
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
代码实现
1234for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
扩展应用
传递闭包
定义
给定一个不包含自环 ...
【笔记/模板】动态规划
前言
动态规划（Dynamic Programming）是c++算法学习当中十分重要而变化灵活的一部分分支，这种算法是通过递推的方式从而达到求出最优解的目的。
动态规划基本原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
最优子结构：每个子问题的解是其本身的最优解。
无后效性：已经求解的子问题，不会再受到后续决策的影响。
动态规划中可能存在大量的子问题造成的答案重叠。
动态规划基本思路
将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的状态与特征。
寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式和关系。
按顺序求解每一个阶段的问题。
背包DP
0-1背包问题
[USACO07DEC]Charm Bracelet S - 洛谷
题目大意：
已知有 nnn 个物品，第 iii 个物品的重量 wiw_{i}wi，价值viv_{i}vi，背包的总容量 WWW。求背包可以容下的最大价值。
解题思路
该类型是典型的背包问题，可以设置一个二维数组 dpi,jdp_{i,j}dpi,j，表示在只能放下 ...
【笔记/模板】Bellman-Ford 与 SPFA
Bellman-Ford求最短路和负环
时间复杂度：O(nm)O(nm)O(nm)
【模板/笔记】Johnson算法
12345678910111213141516171819202122bool Bellman_Ford(){ memset(dist, 0x3f, sizeof dist); for (int k = 1; k < n; k ++) for (int ver = 1; ver <= n; ver ++) for (int i = h[ver]; ~i; i = ne[i]) { int to = e[i]; if (dist[to] > dist[ver] + w[i]) dist[to] = dist[ver] + w[i]; } for (int ver = 1; ver <= n; ver ++) fo ...
【笔记/模板】素数筛
模板原题
1. 寻找因数筛法
时间复杂度：O(nn)O(n\sqrt n)O(nn)
核心模板代码如下：
1234567bool isprime(int n){ if (n < 2) return false; //0和1都不是 for(int i = 2; i * i <= n; ++ i) if(n % i == 0) return false; //有1和它本身以外的其他因子就不是素数了 return true;}
2. 埃氏筛法
时间复杂度：O(nloglogn)O(n\log \log n)O(nloglogn)
核心模板代码如下：
1234567891011121314void Eratosthenes(int n){ vis[0] = vis[1] = true; for (int i = 2; i <= n; i++) { if (!vis[i]) for (int j = 2 * i; j <= n; j += ...