今天是杨思祺老师的讲授~
最短路练习题：
POJ 1125 Stockbroker Grapevine
有 N 个股票经济人可以互相传递消息，他们之间存在一些单向的通信路径。现在有一个消息要由某个人开始传递给其他所有 人，问应该由哪一个人来传递，才能在最短时间内让所有人都接收到消息。
题解：
全局最短路，裸的 Floyd 不用说了，时间复杂度 O （n3）；
POJ 1502 MPI Maelstrom
给出 N 个处理器之间传递信息所需时间矩阵的下三角，求信息 从第一个处理器传到其它所有处理器所需时间最大值。
题解：
我们要建 n2 条边（邻接矩阵），求单元最短路，一遍 Dijkstra 就好了，时间复杂度 O（n2 log n）；
POJ 1511 Invitation Cards
N 个点 M 条边的有向图，询问对于所有 i，从点 1 出发到点 i 并返回点 1 所需时间最小值。
题解：
正向建边，一遍单源最短路求点 1 到每个点的最短路；
那第二问我们总不能每个点都求一遍单源最短路吧 QwQ~
那么我们再反着建边，再来一遍单源最短路求 1 到每个点的最短路就好了 。
POJ 1724 ROADS
有 N 个城市和 M 条单向道路，每条道路有长度和收费两个属性。 求在总费用不超过 K 的前提下从城市 1 到城市 N 的最短路。
题解：
一个比较好像的思路：
我可以将每个点拆成 K+1 个点：
然后跑一遍 Dijkstra，过程中时刻注意花费有没有超过 K 。
神仙做法：
Dijkstra，同时维护当前路径总费用，超过费用上限的状态不再转移。
POJ 1797 Heavy Transportation
给出 N 个点 M 条边的无向图，每条边有最大载重。求从点 1 到点 N 能通过的最大重量。
题解：
1. 我们可以二分答案最大重量 mid，然后我们将所有最大载重小于 mid 的边删掉，然后跑一遍 bfs 判断 1 和 n 是否连通即可；
2. 最大生成树，若加入某条边后 1 和 n 在同一集合里，那么新加入的边的最大载重就是答案；
3. 最短路算法：Dijkstra
d [ u ] 从点 1 到点 u 的最大重量；
那么跑 Dijkstra 的时候我们只要改一下松弛条件就好了：
d [ v ] = min { d [ u ]， w < u , v > } ；
POJ 1062 昂贵的聘礼
年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
题解：
可以这么理解：
我们有了一个东西 u，就能少花点钱，只需要 w 就能买到 v 了；替代关系是边，优惠价格是长度，从某物品出发交换至酋长允诺就是一条路径；
不考虑地位限制，从酋长允诺出发求单源最短路即可知道从任意一点出发所需金币；
枚举地位等级区间，区间长度为 M，不在地位等级区间内的点不可经过，枚举量 O ( N )；
BZOJ 3040 最短路 *
N 个点，M 条边的有向图，求点 1 到点 N 的最短路（保证存在）。 1 ≤ N ≤ 1000000, 1 ≤ M ≤ 10000000
By lydrainbowcat
边集分为两部分：
1. 随机生成；2. 输入给出；
题解：
采用高效的堆来优化 Dijkstra 算法：
斐波那契堆 ；
配对堆；
事实上，忽略随机生成的边（这些边占大部分）亦可得到正确的解。
priority_queue STL 实现合并：
启发式合并，两个堆，A 和 B，把较小的堆砍了，放到较大的堆里面；
每个点最多产生 log n 次代价；
总时间复杂度：O（n ( log n )2）；
最小生成树算法
Prim
Kruskal
Prim
将所有点分为两个集合，已经和点 1 连通的集合 S、未和点 1 连通的集合 T ；
计算集合 T 中每个点 u 和集合 S 的距离：
选取集合 T 中距离 S 最近的点 u，选中对应的边，加入集合 S；
重复上面的过程，直到所有点都被加入集合 S 朴素写法时间复杂度较劣，可以采用堆优化至 O ( ( N + M ) log N )；
正确性的证明：
Prim 是一个基于贪心的算法，可以采用归纳法和反证法证明其正确性。
首先证明第一条选中的边 e1 一定包含在某最优解方案中；
如果最优解中不包含边 e1，则加入 e1 一定会出现环，且环上存在比 e1 大的边，用 e1 替换之答案更优；
假设最优解包含前 k 个选中的边，e1, e2, . . . , ek，则类似地 可证明 ek+1 存在于最优解中；
运用归纳法，Prim 算法得到的 n − 1 条边构成最优解；
Kruskal
将所有边按照边权从小到大排序；
依次考虑每一条边 < ui , vi >，如果这条边和之前选中的边形成环，则不选中此边；反之，选中此边；
当考虑遍所有边后，选中的边一定构成了一棵最小生成树需要并查集的支持，时间复杂度一般认为是 O ( M log M )；
正确性的证明：
证明依赖于拟阵的知识。
拟阵：只要具有遗传性和交换性就说明是个拟阵；
遗传性：若 S 是一个独立集，那么 S 的子集 S ′ 是独立集。
遗传性的推论：空集是独立集。
交换性：若 A 和 B 是 S 的两个独立集且 |A| < |B|（集合元素个数），那么存在一 个元素 x 满足 x A 且 x ∈ B，使得 A ∪ {x} 是一个独立集
交换性的推论：一个集合的所有极大独立集大小都相同。
例：线性无关组、无向图生成森林。
拟阵最优化问题：将集合中每个元素赋予一个权值，求权值和最 小 (大) 的极大独立集。
拟阵最优化的贪心算法：
维护当前独立集 G，初始为空。将元素按照权值排序，从小到大 枚举元素 x，若 G ∪ {x} 是一个独立集，那么就将 x 加入独立集 并将 x 的权值累加入答案。最后的结果就是权值和最小的及大 独立集。
证明： 如果最优解不包含最小元素 x1，记该集合为 A，创建新的集合 B = {x1}，利用交换性不断将 A 中元素加入 B 直到 |A| = |B|， 则有 B 集合为更优解，矛盾。故 x 一定属于最优解。利用数学归纳法，假设已经证明 x1, x2, . . . , xk−1 属于最优解，如果存在最 优解不包含 xk，还是创建新的集合 B {x1, x2, . . . , xk−1, xk }， 利用交换性将元素加入 B 得到更优解，矛盾。
POJ 1258 Agri-Net
有 N 个村庄，村庄之间形成完全图。现给出邻接矩阵，选择总长度尽可能小的边将 N 个村庄连通。
题解：
裸的最小生成树算法，直接 Kruskal；
POJ 2421 Constructing Roads
有 N 个村庄，有一些道路已经存在，现在希望用最少的总长度 将所有村庄连通。
题解：
把存在的道路的边权设置成 0，然后一遍 Kruskal
POJ 2560 Freckles
给出平面上 N 个点，求将所有点连通的最小距离和。
题解：
n2 建边，跑一遍 Kruskal ；
POJ 1789 Truck History
有 N 个编号，每个编号均为 7 位数。两个编号之间的距离定义为其不同位个数，由一个编号生成另一个编号代价为两个编号的 距离。希望用最小总代价从某一编号开始生成所有编号。
题解：
n2 建边，边权是两个编号之间不同位的个数；
BZOJ 1601 灌水
Farmer John 已经决定把水灌到他的 n (1 ≤ n ≤ 300) 块农田，农田被数字 1 到 n 标记。把一块土地进行灌水有两种方法，从其他农田引水，或者这块土地建造水库。建造一个水库需要花费 wi(1 ≤ wi ≤ 100000), 连接两块土地需要花费 pi,j(1 ≤ pi,j ≤ 100000, pi,j = pj,i , pi,i = 0)。
计算 Farmer John 所需的最少代价。
题解：
建立超级水库点，在某点建立水库视为选择长度为 wi 的边将其和超级水库连通，引水就是选择长度为 pi,j 的边。目标是选择长度和尽可能小的边，使得所有点和超级水库连通。
BZOJ 2753 滑雪与时间胶囊
a 来到雪山滑雪，这里分布着 M 条供滑行的轨道和 N 个轨道之间的交点 (同时也是景点)，而且每个景点都有一编号 i 和一高度 Hi。a 能从景点 i 滑到景点 j 当且仅当存在一条 i 和 j 之间的边， 且 i 的高度不小于 j 。a 喜欢用最短的滑行路径去访问尽量多的 景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是 a 拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是 a 滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。现在，a 站在 1 号景点望着山下的目标，心潮澎湃。他〸分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案 (即满足经过景点数最大的前提下使得滑行总距离最小) 。你能帮他求出最短距离和景点数吗？
题解：
能够到达的景点容易通过 DFS 或 BFS 求出。
最优解应当构成树形，所需要的时间即为所有边长度之和。易联想到用最小生成树 Kruskal 算法解决本问题。
如何设置 Kruskal 时边的优先级？如何保证选出的有向边集使得 每个点从 1 出发可达？
以到达点高度为第一关键字，边长度为第二关键字。到达点高度高的边优先，同样高时边长度短的优先。
BZOJ 2561 最小生成树 *
给定一个边带正权的连通无向图 G < V, E >，其中 N = |V|, M = |E|，N 个点从 1 到 N 依次编号，给定三个正整 数 u, v, L (u ≠ v)，假设现在加入一条边权为 L 的边 (u, v)，那 么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
前置技能：网络流最小割
题解：
考虑 Kruskal 的过程，如果加入所有权值小于 L 的边后，u 和 v 连通，则新边不可能出现在最小生成树中；
反之，如果 u 和 v 没有连通，则新边存在于至少一棵最小生成树中。
故加入所有权值小于 L 的边，求从 u 到 v 的最小割，删去这些 边以保证新边可能出现在最小生成树中。
同理，加入所有权值大于 l 的边，再求从 u 到 v 的最小割，删 去这些边使新边可能出现在最大生成树中。 答案即为两次最小割删边数量之和。
树上倍增
有根树（随意定根）
最近公共祖先
链上信息（和、最值）
优秀的时间复杂度
序列倍增
回忆普通的序列倍增思想，以 ST 表为例。
Fi,j 记录区间 [ i, i + 2j − 1 ] 内信息（区间和或区间最值）
Fi,j = merge (Fi,j−1, Fi+2 j−1,j−1 ) # 取出区间 [l, r] 答案时，使用若干个 Fi,j 即可 # 如果求区间最值，那么取 Fl,k 和 Fr−2 k ,k 即可，其中 k ⌊lo g2(r − l + 1⌋ # 如果求区间和，可以取 Fl,k1 , Fl+2 k1 ,k2 , Fl+2 k1+2 k2 ,k3 , . . . 即可
树上倍增
树上从每个点出发到根结点的链也具有类似的形式。
Fi,j 表示点 i 向上走 2j 步的结点编号；
Fi,0 就是点 i 的父亲节点；
如何求解 u 向上移动 k 步是哪个点？
将 k 写作 2 的幂次之和，如 11 = 23 + 21 + 20。 用 Gi,j 表示 i 向上移动 j 步的结果。
在 O( log N ) 步内完成。
最近公共祖先（LCA）
树上倍增最常见的用处是求解两个点的最近公共祖先。
求解 a 和 b 的最近公共祖先 ：
将 a 和 b 调整到相同高度；
判断 a 和 b 是否重合，若重合则该点即为答案；
令 a 和 b 一起向上移动尽可能大的距离，保证移动后两点不重合；
此时两点的父亲结点即为答案，单次询问时间复杂度 O( log N )；
最近公共祖先的常见求解方法有：
1. 树上倍增；
2. 树链剖分；
3. DFS 序 + RMQ；
构造 DFS 序：
我们在 dfs 搜索的时候，假如我们搜到了第 u 个点，我们将 u 放进 dfs 序里面，搜索它的子树然后回溯到点 u 的时候我们再将 u 放进 dfs 序里面，这样算过来一个点 u 在 dfs 序中出现的次数为：（u 的儿子个数 + 1）；
考虑这样一件事情：
我们在 dfs 序中看到了这么一段：
aaaaaysqnpbbbbb
我们发现了一段连续的 a 和 b ；
那么在最后一个a ~ 第一个b 这段区间内，一定有一个是 a 和 b 的 LCA ！
根据 dfs 的顺序可知：递归右子树之前一定会先经过 LCA，那么 LCA 会被扔进 dfs 里面！
所以我们在这一段区间内求出深度最小的点，那个点就是 a 和 b 的 LCA！
向上路径
如何求解从 u 到 v 路径上边权最值？保证 v 是 u 的祖先。
在树上倍增向上走时取移动区间最值更新答案即可。
树上路径
树上路径 记 g = LCA(u, v)，则树上从 u 到 v 的路径可以拆分为两段：
从 u 到 g 的路径；
从 g 到 v 的路径 。
如何求解从 u 到 v 路径上的边权和？
将路径拆分为两段向上路径，分别求解其答案再合并。
树链剖分
树链：不拐弯的路径；
剖分：每个点属于一条链；
应当具有优良的性质。
重儿子：子树大小最大的子结点；
重链：从一点出发，一直选择重儿子向下走，走到叶子；
轻边：不属于任何一条重链的边；
每一条边要么属于重链要么属于轻边；
分析：从任意一点 u 走到根结点，经过的重链、轻边个数的量级是多少？
走一条重链、轻边，子树大小至少翻倍，故易知 O ( log N ) 。