连接 \(i\to i'\)，容量为 \(1\)，表示 \(i\) 至多使用一次
对于所有 \(dp_i=1\) 的 \(i\)，连接 \(S\to i\)，容量为 \(1\)，表示可以从 \(i\) 这个位置开始
对于所有 \(dp_i=L\) 的 \(i\)，连接 \(i'\to T\)，容量为 \(1\)，表示可以从 \(i\) 这个位置结束
对于所有在 dp 过程中能从 \(j\) 转移到 \(i\) 的 \((j,i)\)，连接 \(j'\to i\)，容量为 \(1\)，表示 \(i\) 在子序列中可以接在 \(j\) 的后面

第三问复制第二问的图，如果 \(1\) 能做起点就连接 \(S\to 1,1\to 1'\)，容量为 \(\infty\)，如果 \(n\) 能做终点就连接 \(n\to n',n'\to T\)，容量为 \(\infty\)

注意特判 \(L=1\) 的情况，此时二三问答案均为 \(n\)

Code Link

7. 试题库问题

Problem Link

拆点，设类型 \(i\) 需要 \(f_i\) 道题目，那么我们把 \(i\) 拆成 \((i,1)\sim (i\sim f_i)\)，每个试题向其所有类型的所有点连边

求这个二分图上的最大匹配，判断其大小是否为 \(\sum f_i\) 即可

Code Link

8. 方格取数问题

Problem Link

对网格黑白染色，在相邻的位置之间连边，能够得到一张二分图，答案转化为求这张二分图的最大权独立集

将最大权独立集对偶成点权和减去最小权覆盖集

对于最小权覆盖集，我们可以通过如下方式解决：

对于某个左部点 \(x\)，连接 \(S\to x\)，容量为 \(a_x\)
对于某个右部点 \(y\)，连接 \(y\to T\)，容量为 \(a_y\)
对于某条原本在二分图的边 \((x,y)\)，连接 \(x\to y\)，容量为 \(\infty\)

此时对于原本在二分图中的一条边 \(x\to y\)，在这里被拆成了 \(S\to x\to y\to T\)，我们求出网络上的最小割，那么此时每个 \(S\to x \to y\to T\) 的路径，\(S\to x\) 和 \(y\to T\) 至少有一个在割中，符合覆盖集的定义，因此最小权覆盖集的大小即为网络上最小割的大小

根据最小权点覆盖计算出最大权独立集的大小即可

Code Link

9. 餐巾计划问题

Problem Link

考虑对于每个日期 \(i\) 建立两个节点分别保存当天的干净毛巾和脏毛巾，记为节点 \(i\) 和节点 \(i'\)，构图方式如下：

连接 \(i\to T\)，容量为 \(r_i\)，费用为 \(0\)，表示第 \(i\) 天要供应 \(r_i\) 条毛巾
连接 \(S\to i'\)，容量为 \(r_i\)，费用为 \(0\)，表示第 \(i\) 天结束时可以得到 \(r_i\) 条脏毛巾
连接 \(i'\to(i+1)'\)，容量为 \(\infty\)，费用为 \(0\)，表示第 \(i\) 天可以留下任意多条脏毛巾到下一天清洗
连接 \(i\to(i+1)\)，容量为 \(\infty\)，费用为 \(0\)，表示第 \(i\) 天可以留下任意多条干净毛巾到下一天使用
连接 \(S\to i\)，容量为 \(\infty\)，费用为 \(p\)，表示第 \(i\) 天可以 \(p\) 的单价购买任意多的干净毛巾，当天立即获得
连接 \(i'\to (i+m)\)，容量为 \(\infty\)，费用为 \(f\)，表示第 \(i\) 天可以以 \(f\) 的单价将任意多条毛巾送去快洗，\(i+m\) 天时获得
连接 \(i'\to (i+n)\)，容量为 \(\infty\)，费用为 \(s\)，表示第 \(i\) 天可以以 \(s\) 的单价将任意多条毛巾送去快洗，\(i+n\) 天时获得

我们只需要求出这个网络上的最小费用最大流，其费用即为答案

Code Link

10. 软件补丁问题

Problem Link

对错误状态状压，把每个补丁看成一条边，求最短路即可

Code Link

11. 数字梯形问题

Problem Link

对于问题一：

先对每个位置 \((i,j)\) 拆两个点 \((i,j),(i,j)'\)，然后按如下方式构图：

连接 \(S\to (1,i)\)，容量为 \(1\)，费用为 \(a_{1,i}\)，表示需要恰好一条从 \((1,i)\) 出发的路径，走到 \((1,i)\) 后获得价值 \(a_{1,i}\)
连接 \((i,j)\to(i,j)'\)，容量为 \(1\)，费用为 \(0\)，表示每个点至多被访问一次
连接 \((i,j)'\to (i+1,j)，(i,j)\to (i+1,j+1)'\) ，容量均为 \(1\)，费用分别为 \(a_{i+1,j},a_{i+1,j+1}\)，表示走到下一层的两个位置获得相应的价值
连接 \((n,i)'\to T\)，容量为 \(1\)，费用为 \(0\)，表示至多一条路径以 \((n,i)\) 结尾

对于问题二：

不需要拆点，按如下方式构图：

连接 \(S\to (1,i)\)，容量为 \(1\)，费用为 \(a_{1,i}\)，表示需要恰好一条从 \((1,i)\) 出发的路径，走到 \((1,i)\) 后获得价值 \(a_{1,i}\)
连接 \((i,j)'\to (i+1,j)，(i,j)\to (i+1,j+1)'\) ，容量均为 \(1\)，费用分别为 \(a_{i+1,j},a_{i+1,j+1}\)，表示每条边至多被走一次，走到下一层的两个位置获得相应的价值
连接 \((n,i)\to T\)，容量为 \(\infty\)，费用为 \(0\)，表示任意条路径以 \((n,i)\) 结尾

对于问题三：

不需要拆点，按如下方式构图：

连接 \(S\to (1,i)\)，容量为 \(1\)，费用为 \(a_{1,i}\)，表示需要恰好一条从 \((1,i)\) 出发的路径，走到 \((1,i)\) 后获得价值 \(a_{1,i}\)
连接 \((i,j)'\to (i+1,j)，(i,j)\to (i+1,j+1)'\) ，容量均为 \(\infty\)，费用分别为 \(a_{i+1,j},a_{i+1,j+1}\)，表示每条边可以走任意次，走到下一层的两个位置获得相应的价值
连接 \((n,i)\to T\)，容量为 \(\infty\)，费用为 \(0\)，表示任意条路径以 \((n,i)\) 结尾

三个问题的答案分别为这三个网络上的最大费用最大流的费用

Code Link

12. 运输问题

Problem Link

按如下方式构图：

对于每个仓库 \(i\)，连接 \(S\to i\)，容量为 \(a_i\)，费用为 \(0\)，表示第 \(i\) 个仓库里有 \(a_i\) 件货物
对于每个商店 \(j\)，连接 \(j\to T\)，容量为 \(b_i\)，费用为 \(0\)，表示第 \(j\) 个商店需要 \(b_i\) 件货物
对于每个仓库 \(i\) 和商店 \(j\)，连接 \(i\to j\)，容量为 \(\infty\)，费用为 \(c_{i,j}\)，表示从第 \(i\) 个仓库到第 \(j\) 个商店可以以 \(c_{i,j}\) 的单价运输任意数量的货物

两个问题的答案即分别为这个网络上的最小费用最大流和最大费用最大流

Code Link

13. 分配问题

Problem Link

人看成左部点，任务看成右部点，最大价值直接求二分图最大权完美匹配即可

最小价值可以选取一个足够大的值 \(A\)，把每条边的边权看成 \(A-c_{i,j}\) 满足 \(A-c_{i,j}\ge 0\) 求出最大权完美匹配的大小 \(x\)，答案即为 \(n\times A-x\)

Code Link

14. 负载平衡问题

Problem Link

先求出 \(\{a_i\}\) 的平均值 \(\bar a\)，然后按如下方式构图

对于每个 \(a_i>\bar a\) 的 \(i\) 连接 \(S\to i\)，容量为 \(a_i-\bar a\)，费用为 \(0\)，表示 \(a_i\) 变成 \(\bar a\) 需要有 \(a_i-\bar a\) 件货物被运出
对于每个 \(a_i<\bar a\) 的 \(i\) 连接 \(i\to T\)，容量为 \(\bar a-a_i\)，费用为 \(0\)，表示 \(a_i\) 变成 \(\bar a\) 需要有 \(\bar a-a_i\) 件货物被运入
连接 \(i\to i+1,i\to i-1\)，容量为 \(\infty\)，费用为 \(1\)，表示可以以 \(1\) 的单价将任意多件 \(i\) 中的货品运到 \(i-1\) 或 \(i+1\) 上