#! https://zhuanlan.zhihu.com/p/598626208 # DW分解（Dantzig-Wolfe decomposition）和benders分解 DW分解（Dantzig-Wolfe decomposition） 对于标准形式的线性规划，也就是 \[ \min c^T x \\ {s.t.}\left \{ \begin{array}{l}

#! https://zhuanlan.zhihu.com/p/598134928 # 分支定界法与分支定价法 分支定界法（Branch and bound） 分支定界法一般用于解决整数线性规划和混合整数线性规划。它本质上是一种基于搜索的算法，是比较暴力的，并且在极坏情况下可能会退化成枚举。 对于如下混合整数线性规划问题 \[ \min_{x,y} f(x,y) \\ {s.t.}\lef

#! https://zhuanlan.zhihu.com/p/598065618 # 割平面法（行生成算法）与列生成算法以及它们的对偶性 在线性规划中，我们把变量称为“列”，把约束称为“行”。行生成和列生成算法大思路是一致的，都是由于原问题规模过大，所以需要把原问题“简化”一部分，不过这就导致丢失了部分信息，失去了最优性。因此我们就要以某种方式迭代的把简化掉的部分再添加回去一部分，直到得到最优解

#! https://zhuanlan.zhihu.com/p/597492395 # 从Lagrange对偶到线性规划对偶问题 Lagrange对偶 我们熟悉Lagrange乘子法，它是求解带有等式约束的最值问题的方法，而Lagrange对偶函数可以理解为是它的一种拓展，它能解决带有等式和不等式约束的问题，也就是标准形式的优化问题。标准形式的优化问题形如 \[ \min f_0(x) \\

#! https://zhuanlan.zhihu.com/p/597955786 # 线性规划对偶问题、影子价格（shadow price）与单纯形法检验数（reduce cost） Lagrange对偶问题（包括线性规划对偶问题）实际上可以有一个经济学的解释（关于Lagrange对偶、线性规划对偶的数学推导可以看上一篇文章）。对于这样一个原问题 \[ \min f_0(x) \\ {s

#! https://zhuanlan.zhihu.com/p/597399183 # 共轭函数（Legendre变换与Fenchel变换） Legendre变换是物理（力学，热力学），数学中常用的一种变换。它把可微凸函数从关于原自变量x的函数变为关于点导数（梯度）的函数。也就是如果记\(k=\dfrac{df}{dx}\)，那么把原函数\((x,f(x))\)变换为\((k,f^*(k))\)。

#! https://zhuanlan.zhihu.com/p/596106342 # 两种TSP问题（旅行推销员问题）的复杂性证明 我们平时说的TSP问题实际上有两种，一种是原始版本，我们称之为tour-TSP。它要求从某个点出发，经过每个点一次，然后再回到原点。另一种是变种path-TSP，它使得可以从任意点出发，并且经过每个点一次，最终不需要回到原点。实际上可以证明这两个问题有相似的复杂性。

求次短路 很好想，在spfa的基础上添加一个数组即可，就是转移的时候要注意。 1234567891011121314151617181920212223242526void spfa(int u){ for(int i=1;i<=n;i++){ d[i]=inf;d2[i]=inf; } d[u] = 0; q.push(u); while(!q.empty(

T1：贪婪地送礼者 枚举每个人，把钱送出去就好了，然后统计答案即可。 T2： [USACO1.1]黑色星期五Friday the Thirteenth 13号又是一个星期五。13号在星期五比在其他日子少吗?为了回答这个问题,写一个程序，要求计算每个月的十三号落在周一到周日的次数。给出N年的一个周期，要求计算1900年1月1日至1900+N-1年12月31日中十三号落在周一到周日的次数，N为正整数

拿到这道题应该很容易想到排序。关键是如何处理排序之后原序中只能往右走这个信息。 考虑这样做，在排序好的数组中，离一个点i最近和次进的一定在i-1,i-2,i+1,i+2中。只用处理这四个即可。问题是如何使序合法。 有一种优雅的解法是在排好序的数组中找到原序为1的点，处理好离他最近和次近的点。这样处理出的一定是合法的，因为数组中不存在比它还左的点。处理完后删掉这个点，这样第二个点就变成数组中最左的点