计算几何

无

树套树 1

图论 1

图论 2

无

见专题部分

字符串基础

字符串匹配

字符串哈希

字典树(Trie)

前缀函数与 KMP 算法

无

洛谷p1742

最小圆覆盖模板

洛谷p5192

网络流

一个摄影师，$n$ 天时间，$m$ 个取材对象。要求 $n$ 天后第 $x$ 个取材对象至少需要取材 $G_x$ 张照片。

第 $k$ 天可以取材 $C_k$ 个对象，总共可以取材 $D_k$ 张照片，当天每个可取材对象的取材照片数量必须在区间 $[L_{k_i},R_{k_i}]$ 内。

问是否存在满足条件的方案，如果存在输出总共可以取材的最大照片数，如果不存在输出 $-1$。

把天和取材对象都当成一个节点，建有源上下界网络流图。

$n$ 天后第 $x$ 个取材对象至少需要取材 $G_x$ 张照片可以理解为第 $x$ 个取材对象代表节点向汇点连一条上下界为 $[G_x,\inf]$ 的边。

第 $k$ 天总共可以取材 $D_k$ 张照片可以理解为源点向第 $k$ 天代表节点连一条上下界为 $[0,D_k]$ 的边。

第 $k$ 天可取材对象的取材照片数量必须在区间 $[L_{k_i},R_{k_i}]$ 内可以理解为第 $k$ 天代表节点向第 $k_i$ 个取材对象连一条上下界为 $[L_{k_i},R_{k_i}]$ 的边。

最后求一下有源汇上下界的最大流即可。

一道不错的有源汇上下界最大流练习题。