模板类

分别是最大流，最小费用流的模板题，无建模难度

我跑最大流和最小费用流用的是预流推进和原始对偶

二分图匹配

二分图匹配模板题。

对每个飞行员建一个点，建源 \(S\)，汇 \(T\)，\(S\) 连英国飞行员，\(T\) 连外籍飞行员，每有一个配对关系就在两飞行员的点间连边，边权均为 \(1\)，跑最大流，两飞行员间若边有流量则他们配对。

对每个单位和桌子建点，单位连源 \(S\)，桌子连汇 \(T\)，边权为单位的人数/桌子的人数，单位和桌子间连边，边权为 \(1\)，代表这个单位只能去 \(1\) 个人到某个桌子
，跑最大流即可，输出类似上题。

源连题权为 \(1\)，题连类型权为 \(1\)，类型连汇权为要选的该类型题数，跑最大流。

对人和工作建点，人连源 \(S\)，工作连汇 \(T\)，边权为 \(1\) 代表每个人只能有一份工作，费用为 \(0\).

人 \(i\) 和工作 \(j\) 间连边，边权为 \(1\)，费用为 \(-c_{i,j}\)，跑最小费用流。

这类题都要求最短时间

每个错误是否有状压为一个 int，不同的状态间连边对应补丁（应用补丁后状态发生变化）长度对应补丁的时间，跑最短路。

需要注意的是，由于状态数过多，不必真的连边，每次转移时枚举补丁即可。

将坐标和有无钥匙塞到一个 std::tuple 里，每次状态变化依赖于坐标和有无钥匙，跑最短路。

由于边权均为 \(1\)，也可 BFS.

餐巾计划问题
汽车加油行驶问题
最小路径覆盖问题
太空飞行计划问题
航空路线问题
魔术球问题
最长不下降子序列问题
星际转移问题
方格取数问题
数字梯形问题
深海机器人问题
最长k可重线段集问题
骑士共存问题
火星探险问题
志愿者招募