最小费用最大流，指在保证最大流量的同时最小费用。

Description

题目链接：Luogu 2756

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 $2$ 名飞行员，其中 $1$ 名是英国飞行员，另 $1$ 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。皇家空军共有 $n$ 名飞行员，其中 $m$ 名为外籍飞行员。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

数据范围：$1\le m\le m<100$

Description

题目链接：Luogu 1080

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

数据范围：$1\le n\le 10^3$，$0<a,b<10^4$

Description

题目链接：BZOJ 2127

高一一班的座位表是个 $n\times m$ 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。

作为计算机竞赛教练的 scp 大老板，想知道如何分配可以使得全班的喜悦值总和最大。

数据范围：$1\le n,m\le 100$，喜悦值均为小于等于 $5000$ 的非负整数。

Description

题目链接：Luogu 5110

给定一个数列 $a$ 满足递推式：

$$a_n=233\times a_{n-1}+666\times a_{n-2},a_{0}=0,a_{1}=1$$

求这个数列第 $n$ 项 $a_n\bmod (10^9+7)$ 的值，一共有 $T$ 组询问。为了减少你的输出量，你只需要输出所有询问答案的异或和。

数据范围：$0\le n<2^{64}$，$1\le T\le 5\times 10^7$

Description

题目链接：Luogu 2763

假设一个试题库中有 $n$ 道试题，试题被分为 $k$ 个类型。每道试题都标明了所属类别，同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷，每道题只能被选择一次。给出每个类型需要的题数，试设计一个满足要求的组卷方案。

数据范围：$2\le k\le 20$，$k\le n\le 1000$

Description

题目链接：Luogu 1345

农夫约翰的奶牛们喜欢通过电邮保持联系，于是他们建立了一个奶牛电脑网络，以便互相交流。这个网络包括 $n$ 台电脑和 $m$ 个电脑之间的连接。这些电脑用如下的方式发送电邮：如果存在一个由 $c$ 台电脑组成的序列 $a_1,a_2,\dots,a_c$，且 $a_1$ 与 $a_2$ 相连，$a_2$ 与 $a_3$ 相连……那么电脑 $a_1$ 和 $a_c$ 就可以互发电邮。

很不幸，有时候某些倒霉的电脑会坏掉。说这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。

有两头奶牛就想：如果我们两个不能互发电邮，至少需要坏掉多少台电脑呢？你需要计算出这个最小值。

数据范围：$1\le n\le 100$，$1\le m\le 600$

Description

题目链接：BZOJ 1001

现在小朋友们最喜欢的”喜羊羊与灰太狼”，话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为 $(1,1)$，右下角点为 $(n,m)$（上图中 $N=3,M=4$）。有以下三种类型的道路：

1. $(x,y)\longleftrightarrow(x+1,y)$
2. $(x,y)\longleftrightarrow(x,y+1)$
3. $(x,y)\longleftrightarrow(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里，现在它们要跑到右下角 $(N,M)$ 的窝中去，狼王开始伏击这些兔子.当然为了保险起见，如果一条道路上最多通过的兔子数为 $K$，狼王需要安排同样数量的 $K$ 只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。

数据范围：$1\le N,M\le 1000$

Description

题目链接：Luogu 4011

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 $N$ 行，东西方向被划分为 $M$ 列，于是整个迷宫被划分为 $N\times M$ 个单元。每一个单元的位置可用一个有序数对（单元的行号，单元的列号）来表示。南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成 $P$ 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 $(N,M)$ 单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入 $(1,1)$ 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 $1$，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

数据范围：$1\le N,M,P\le 10$

Description

题目链接：Luogu 4662

Byteland 国警方收到了一条匿名举报，其中说当地黑帮老大正计划一次从港口到郊区仓库的运输。警方知道运输的时间并且知道运输需要用到国家的高速公路网。

高速公路网包含 $n$ 个收费站和 $m$ 条双向的高速公路，每个路段直接连着两个不同的收费站。一个收费站可能与很多其他的收费站相连。汽车只能通过收费站进入或离开高速公路网。据所知，黑帮会距港口边最近的收费站进入高速公路，从距仓库最近的收费站离开（不会在出高速后重新进入）。特警组位于选定的收费站处。当运输车辆进入被监控的收费站时，它就会被警察抓住。

从这个角度看，最简单的办法就是在每个收费站处都安排特警班。然而，控制第 $i$ 个收费站需要特定的费用 $c_i$，每个收费站费用不同。警方想要让花费最小，所以他们需要制定一个收费站的最小控制集，这个集合满足两个条件：

• 所有从港口到仓库的交通必须至少经过集合中的一个收费站。
• 监控这些收费站的费用（即监控每一个收费站费用之和）最小。
• 你可以假设使用高速公路可以从港口到仓库。

你需要找到收费站的最小控制集。

数据范围：$1\le n\le 200$，$1\le m\le 2\times 10^4$，$1\le c_i\le 10^7$