给定一个由 $n$ 行数字组成的数字梯形如下图所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

1. 从梯形的顶至底的 $m$ 条路径互不相交；
2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交；
3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为 $P$ 分；或者把旧餐巾送到快洗部，洗一块需 $M$ 天，其费用为 $F$ 分；或者送到慢洗部，洗一块需 $n$ 天，其费用为 $S$ 分（$S<F$）。

每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

在一个有 $m\times n$ 个方格的棋盘中，每个方格中有一个正整数。

现要从方格中取数，使任意 $2$ 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

众所周知，最小费用最大流向来是一个算法很多的问题，下面总结了几个常用的最小费用最大流算法。

给定正整数序列 $x_1\sim x_n$ ，以下递增子序列均为非严格递增。

1. 计算其最长递增子序列的长度 $s$ 。

2. 计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。

3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ ，则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。

假设有来自 $m$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$ 。会议餐厅共有 $n$ 张餐桌，每张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法，给出满足要求的代表就餐方案。

假设有 $n$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1,2,3,4,\cdots$ 的球。

1. 每次只能在某根柱子的最上面放球。
2. 在同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。

给定有向图 $G=(V,E)$。设 $P$ 是 $G$ 的一个简单路（顶点不相交）的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。 $P$ 中路径可以从 $V$ 的任何一个顶点开始，长度也是任意的，特别地，可以为 $0$ 。 $G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E=E_1,E_2,\cdots ,E_m$ ，和进行这些实验需要使用的全部仪器的集合 $I=I_1,I_2,\cdots ,I_n$ 。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j\subseteq I$ 。配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。W 教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员，需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格，两个正驾驶员或两个副驾驶员都不能同机飞行。

我们有 $n$ 个集合，第 $i$ 个集合有 $m_i$ 个数（$1$ 到 $n$ 中的整数），权值为 $w_i$ 。

现在请你从中选出 $k$ （$k$ 为任意 $0$ 到 $n$ 中的整数）个集合，满足这 $k$ 个集合的并集的大小为 $k$ ，询问这 $k$ 个集合的权值和最小值。

保证从这 $n$ 选出任意 $x$ 个集合，他们的并集大小不小于 $k$ 。

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。

在前期市场调查和站址勘测之后，公司得到了一共 $N$ 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 $i$ 个通讯中转站需要的成本为 $P_i$ 。

另外公司调查得出了所有期望中的用户群，一共 $M$ 个。关于第 i 个用户群的信息概括为 $A_i$ , $B_i$ 和 $C_i$ ：这些用户会使用中转站 $A_i$ 和中转站 $B_i$ 进行通讯，公司可以获益 $C_i$ 。

THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）

题面请点击查看全文

给定一张有向图，每条边都有一个容量 $C$ 和一个扩容费用 $W$ 。这里扩容费用是指将容量扩大 $1$ 所需的费用。

现在请你编写一个程序求出：

1. 在不扩容的情况下， $1$ 到 $N$ 的最大流；
2. 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。