基本原则  首先看题目n的数量级，当 n<1000 时，可以使用 [Floyd算法] 快速秒杀几乎所有题型 否则 若题目中所有边全为正权，则使用 [Dijkstra算法] 否则 当出现负权时，使用 [spfa算法] 注意一些隐蔽的最短路问题，比如题目会换一种问法。详见最短路的各种变形题。   一、正权单源最短路 —— Dijkstra算法 1. 定义 计算正权图上的单源最短路，即从单个源点出发到所有结点的最短路。包含无向图或有向图。 2. 解析 使用Dijkstra算法。时间复杂度O(mlgn)，一般够用。 3. 模板 struct node { // node结构是存放在优先队列中的结...

一、题意 给出一个n（n<=100）结点的图，求苗条度（最大边减最小边的值）尽量小的生成树 二、解析 其实就是要求边权极差最小的生成树。我们知道求最小生成树是用Kruskal算法，这里其实也是一样：我们枚举生成树的最小边E[l]，然后每次只从边权大于这条最小边边权的边中进行最小生成树的生成，这样就能得到这个生成树的最大边边权。这样枚举完后，我们就能得到边权极差最小的生成树了。 正确性证明：为什么最小生成树T就一定是这个最小边对应的苗条度最小的生成树呢？仔细回想一下Kruskal算法，最小生成树T是通过从小到大枚举边得到的，如果这个最小边对应的使得苗条度最小的最大边不在这个T中的话，那就是...

一、题意 输入一个n个点m条边的图，要求你计算出图中的最小生成树和次小生成树的权值和。 二、解析 最小生成树比较简单，直接上Kruskal算法模板即可。主要是次小生成树应该如何求解？ 其实也比较简单，按照以下步骤即可：  求出最小生成树mst 通过以每个点为根分别进行dfs，得到maxW[maxn][maxn]数组。其中maxW[root][v]表示最小生成树mst上从root到v的路径上的最大的一条边的权值。 遍历所有不在mst上的边，比如为（u, v），用它去替换mst上从u到v路径上的最大边，从而得到一系列次小生成树替补。这些次小生成树替补权值和最小的那个就是次小生成树。  时间复杂度为...

一、题意 输入n表示有n个点，然后输入每个点的实数坐标（xi, yi），求连通所有点的最小长度和。 二、解析 这是一道裸的最小生成树问题，边权就是两点间的距离。直接上Kruskal算法模板。总是得来一道模板题复习复习的。 三、代码 #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <iomanip> using namespace std; const int maxn = 100 + 5; struct edge ...

基本定义 本文的代码基本按照如下的图论模型进行定义，后文用的结构若与此相同则不再赘述： struct edge { int u, v, w; edge(int u, int v, int w) : u(u), v(v), w(w) {} bool operator < (const edge& rhs) const { // 边按权值排序 return w < rhs.w; } }; vector<edge> E; // 存储所有边 int n, m, Fa[maxn]; // Fa为并查集所需的数组 int find(int x) { // 并查集的find函...

一、枚举排列 1. 定义 枚举出一个序列a[maxn]的所有排列。 2. 解析 枚举排列 最简单的方法是运用STL的 next_permutation函数. 3. 模板 int a[maxn]; int main(){ ...... sort(a, a + n); do{ for(int i = 0; i < n; i ++) cout << a[i] << " "; // 打印排列 cout << endl; } while(next_permutation(a, a + n)); }  二、枚举集合 1. 定义 枚举出一个序列a...

一、滑动窗口 1. 定义 滑动窗口法（又叫双指针法），即用i,j双指针（一般用下标）对数组进行遍历，同时要需要一个额外的比如vis数组维护窗口中的元素信息，是一种O(n)的扫描方法。 2. 解析  一般比较常见的问题就是，维护窗口中的元素各不相同。既可以用一个vis[maxn]数组来表示窗口中是否存在某个元素，也可以用一个pos[maxn]数组来存储上一次遇见某个元素的位置（为-1表示不在窗口中）。本质是一样的。 当元素数值比较大时，用unordered_map来实现vis或pos即可。 最好统一一下开闭区间，比如总是使用闭区间[i, j]作为窗口范围。 最好统一一下判断顺序，比如总是先处理当...

一、01背包问题 1. 定义 有n件物品和一个容量为V的背包。第i件物品的体积（volumn）是v[i]，价值（worth）是w[i]，问如何选择物品装入背包可使价值总和最大。 2. 解析  每种物品只有选和不选两种。我们可以使用多阶段动态规划的思想来解决。用dp[i][j]表示前i个物品（或用“从第i个物品开始的后面所有物品”的反向定义也行）装入容量为j的背包中的最大价值量。则转移方程为：其中每多考虑一个物品i，代表一个“阶段”。括号第一项表示选，第二项表示不选。 （优化）由于每一项都是依赖于i-1，因此可以使用滚动数组来优化空间复杂度：其中注意使用滚动数组时，j的遍历必须逆序，来保证等号右...

基本定义  区间用一个结构体来表示：  struct Internal { int l, r; bool operator < (const Internal& rhs) const { return ......; // 按左端点 或 右端点 或其它排序 } }; vector<Internal> vec; // 存放所有区间的容器 以下代码只使用一个int类型的ans进行计数，若题目需要打印出所选择的区间/点，则改成用一个vector类型的ans存储即可。   一、区间不相交问题 1. 定义 数轴上有n个区间（li, ri），选择尽量多的区间，使得这些区间两两不相...

一、题意 有6堆石头，第i堆石头中每个石头的价值都是i。然后输入每堆石头的数量num[i]。要求你判断是否可以将所有石头分成总价值相等的两堆。 二、解析 首先算出所有石头的总价值V，若V为奇数，则无解。若V为偶数，则我们的目标就是拿一个体积为V/2的背包，然后尽可能装满它。若装得满，说明原问题可以分成价值相等的两堆，否则不能。 由于每种价值的石头有数量限制，因此这是一个多重背包问题。在本题对应的背包问题中，物体（也就是石头）的价值和体积都是V[i]。于是我们套用完全背包的模板即可。 一般情况下，完全背包问题使用二进制法就基本不会超时了，它的原理就是将一个数量为p[i]，价值为v[i]的物体拆分...

一、题意 输入包含多组测试用例。每组数据以一个整数n开始，表示每天的食物清单有n种食物。接下来n行，每行两个整数a和b，其中a表示这种食物可以带给湫湫的幸福值（数值越大，越幸福），b表示湫湫吃这种食物会吸收的卡路里量。最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。输出最大幸福值。 二、解析 这是一到换了皮的裸完全背包问题。转化一下题意就是：有n种物品，每种物品数量无限，每种物品的价值和体积分别为w[i]和v[i]。现在给一个体积为V的背包，要求输出最多能装入的价值量。 这里主要是复习一下完全背包问题的两种解题思路：  方法一：看作DAG问题求解。 这种方法我是根据紫薯的提示学到的，即把...

一、题意 给一个V（V<=10000）和一个n（n<=20），V代表磁带的最大长度，n表示n首曲子，然后给出每首曲子的长度，现在要求你选一些曲子放入磁带中，使得磁带的利用率最高，输出最终磁带中存放的曲子序列，并输出总长度。 二、解析 换了个皮也得认出这是一个01背包问题。翻译过来就是：往体积为V的背包里放物品，n个物品的体积给出，在本题中体积也是价值，然后尽可能使背包里物品的总价值最大。直接套用01背包问题的转移方程：dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i])在本题中体积就是价值，所以即为 dp[i][j] = ...

一、题意 给一个n行m列的整数矩阵（n<=10, m<=100），从第一列的任何一个位置出发，每次可以往→、↗、↘走一格，最终到达最后一列。矩阵时环形的，即第一行的上一行是最后一行，最后一行的下一行是第一行。现在要你找一条路线使得经过的数字之和最小。打印出路径和最小和。若有多解则输出字典序最小的。 二、解析 这是一道多阶段决策问题，一般这种问题都可以通过递推法的动态规划解决。 用dp[i][j]表示从a[i][j]开始的路径到达最后一列的最小和，的转移方程可以很容易得到：即dp[i][j]=a[i][j]+min(dp[→]，dp[↗]，dp[↘])。 这道题还要输出路径。这里主要...

一、题意 给定金额n，有50, 25, 10, 5, 1这五种面值的钱，问共有多少种不同的找法。 二、解析 看到这道题，第一反应是用DAG的记忆化搜索法求解，即每个金额V指向V-coins[i]。但这样会出现一个问题，就是重复计数的问题。比如16块钱，10->5->1的找法和1->5->10的找***被当作不同的找法，这是不对的。如果用递推法中的填表法也是一样，无法避免重复计算的问题。 这个时候就得使用递推法中的“刷表法”了。 即用每一种面值的纸币coins[i]去分别“更新”每一种金额j的找法数量dp[j]。比如，当只有10这个面值时，找10块钱金额只有 10 一种找...