一种构造方法，仅 $532$ 个点，$24115$ 条边的图，使得 Dinic, SAP, ISAP 运行时间均大于 $1s$，
$1198$ 个点，$120796$ 条边运行时间均超过 $1 \mathrm{min}$（当然也可能是我的最大流写得太菜）。

给出一个无向图，对于每条边，求必须选择这条边的情况下，使得原图连通的最小代价。

T2 Game

甲乙两个人轮流那一些物品，甲先手，他可以拿走 $1$ 或 $2$ 个物品。对于后面，若前一个人拿走 $k$ 个物品，当前的人可以拿走 $k$ 或 $k + 1$ 个物品，甲乙的策略都是让自己尽量比别人拿的物品的价值高，求最优策略下，甲最多比乙多拿多少？

T1 建设图

给出一个无向图，求最少添加多少条边使得，无论删掉哪条边任意两点都可以互相到达。

地主的傻儿子豆豆家很大很大，由很多个区域组成。其中有不少封闭的区域，豆豆觉得很不爽于是决定拆墙，把家打通使得他可以访问到每一个区域（包括家外面无限大的区域）。我们用 $N$ 个端点和 $M$ 条边来描述豆豆的家。第 $i$ 个端点的坐标为（$x_i, y_i$）,第 $i$ 条边连接端点 $A_i$ 和 $B_i$，拆除所需要花费的力气为 $C_i$ 。保证所有边只在端点相交，也就是这是一个平面图，也没有重边和自环。

现在豆豆想知道他最少一共需要花费多少力气？

给出一个 $n * n$ 的黑白方阵，问能否通过交换行或交换列使得主对角线均为黑色。

给出一个 $n$ 个点 $m$ 条边的无向图，每个边有一正一反两个权值；现要从点 $1$ 出发，对每条边经过且仅经过一次；求一种方案使经过的最大权值最小。

一些 2-SAT 题目。

复习 Tarjan 算法以及一些常见的应用。

有 $K$ 个棋子在一个大小为N×N的棋盘。一开始，它们都在棋盘的顶端，它们起始的位置是 $(1, a_1),(1, a_2),…,(1, a_k)$，它们的目的地是 $(n, b_1), (n, b_2),…,(n, b_k)$。

一个位于 $(r,c)$ 的棋子每一步只能向右走到 $(r, c + 1)$ 或者向下走到 (r + 1, c)$。

我们把 $i$ 棋子从 $(1, a_i)$ 走到 $(n, b_i)$ 的路径记作 $p_i$。

你的任务是计算有多少种方案把 $n$ 个棋子送到目的地，并且对于任意两个不同的棋子 $i,j$，使得路径 $p_i$ 与 $p_j$ 不相交（即没有公共点）。

Ben 最近学习了二进制信息。一条二进制信息由 $n$ 个二进制码组成，第 $i$ 个二进制码记为 $s_i$ 。二进制码就是一个只包含 ′0′ 和 ′1′ 的字符串。一条二进制信息被称为“漂亮的二进制信息”当且仅当对于任意的 $i \neq j$，$s_i$ 都不是 $s_j$ 的前缀。二进制码 $x$ 是二进制码 $w$ 的前缀当且仅当存在一个二进制码 $y$ （长度可以为 $0$），使得 $xy = w$ ，例如 $x = 11$ 是 $w = 110$ 的前缀，$x = 0100$ 是 $w = 0100$ 的前缀。

Ben找到一张纸，上面写着二进制信息。可是，这张纸有点旧了，有些字符看不清。但是很幸运，每个二进制码都只包含最多一个看不清的字符。

Ben 想知道这 $n$ 个二进制码能否表示一条“漂亮的二进制信息”。也就是说，是否存在一种方案，用 ′0′ 或 ′1′ 替换那些看不清的字符，使得这条信息变为漂亮的二进制信息。

从前，有一只懒猫叫 $CJB$。每个小时，这只猫要么在睡觉，要么在吃东西，但不能一边睡觉一边吃东西，并且这只猫会在一整个小时干同一件事情。

对于接下来的 $n$ 个小时，$CJB$ 知道他在哪 $n$ 个小时睡觉和吃东西的快乐值。

为了健康地生活，在任意的连续 $k$ 个整小时内，$CJB$ 要有至少 $m_s$ 小时睡觉，至少 $m_e$ 个小时在吃东西。也就是说一共有 $n - k + 1$ 段的 $k$ 小时需要满足上述条件。

你的任务是告诉 $CJB$ 他接下来 $n$ 个小时能获得的最大快乐值是多少。

一次舞会有 $n$ 个男孩和 $n$ 个女孩。每首曲子开始时，所有男孩和女孩恰好配成 $n$ 对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和 $k$ 个不喜欢的女孩跳舞，而每个女孩也最多只愿意和 $k$ 个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.

Farmer John’s farm has $N$ barns, and there are some cows that live in each barn. The cows like to drop around, so John wants to build some roads to connect these barns. If he builds roads for every pair of different barns, then he must build $N * (N - 1) / 2$ roads, which is so costly that cheapskate John will never do that, though that’s the best choice for the cows.

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 \leq c \leq 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 \leq Xi \leq 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:…