给出一个无向连通图，求所有点对的最小割数值中不同的个数。

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

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

游戏中有 $N$ 个剧情点，由 $1$ 到 $N$ 编号，第 $i$ 个剧情点可以经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

开始处在 $1$ 号剧情点。任何一个剧情点都是从 $1$ 号剧情点可达的。从任意剧情点出发，都不能再回到这个剧情点。要想回到之前的剧情点，唯一的方法就是开始新的游戏，回到 $1$ 号剧情点。可以在任何时刻退出游戏并重新开始。求花费最少的时间，看完所有不同的支线剧情。

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

有 $X, Y$ 两类卡牌，分别有 $n_1, n_2$ 张，每张卡牌有三个属性值：$A, B, C$。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。

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

一些 2-SAT 题目。

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:…

Up to thirty couples will attend a wedding feast, at which they will be seated on either side of a long table. The bride and groom sit at one end, opposite each other, and the bride wears an elaborate headdress that keeps her from seeing people on the same side as her. It is considered bad luck to have a husband and wife seated on the same side of the table. Additionally, there are several pairs of people conducting adulterous relationships (both different-sex and same-sex relationships are possible), and it is bad luck for the bride to see both members of such a pair. Your job is to arrange people at the table so as to avoid any bad luck.

Being a knight is a very attractive career: searching for the Holy Grail, saving damsels in distress, and drinking with the other knights are fun things to do. Therefore, it is not very surprising that in recent years the kingdom of King Arthur has experienced an unprecedented increase in the number of knights. There are so many knights now, that it is very rare that every Knight of the Round Table can come at the same time to Camelot and sit around the round table; usually only a small group of the knights isthere, while the rest are busy doing heroic deeds around the country.

The $N (2 <= N <= 10,000)$ cows are so excited: it’s prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance.

Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.

Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, $3$, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes $1$ and $2$ could still communicate with each other as could nodes $4$ and $5$, but communication between any other pairs of nodes would no longer be possible.

为了从F($1 \leq F \leq 5000$)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树．奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择．

每对草场之间已经有至少一条路径．给出所有R($F-1 \leq R \leq 10000$)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量, 路径由若干道路首尾相连而成．两条路径相互分离，是指两条路径没有一条重合的道路．但是，两条分离的路径上可以有一些相同的草场． 对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路．

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务：

1. 这张图是无向图。（$50$ 分）
2. 这张图是有向图。（$50$ 分）

SPFA【SLF优化】

SLF

Small Label First 策略，设要加入的节点是j，队首元素为i，若dis[j] < dis[i]，则将j插入队首，否则插入队尾，可能会被卡到指数级复杂度。

题目描述

给定一个一定存在从起点到终点的路径的四联通迷宫。已知 Tar 左右方向移动的时间为 1 ，上下移动的时间为未知实数 v 。求当 Tar 从起点到终点的最短移动时间为已知实数 L 时，未知实数 v 是多少。

加边

题目描述

给出一个 N×M 的矩阵，在这个矩阵上的每一个点都有一个高度值 h 。矩阵中相邻两点是连通的，而且只能从高度高的点到达高度低的点，高度相同的点之间可以相互到达。
现在要求在图中连若干双向边，使图中任意一点 u 出发都可以到达任意的其它点 v ，问至少需要连接多少条双向边？

输入格式

第一行是两个整数：（1 \leq N,M \leq 300），其中, N，M分别表示矩阵的行数和列数。
从第二行开始，描述的是一个 N 行 M 列的矩阵，矩阵每个位置上的数字表示该位置的高度 h（1 \leq h \leq 1,000,000）。

输出格式

输出一个整数，即至少需要连接的边的数量。

最佳路线

题目描述

N 个景区，任意两个景区之间有一条或多条双向的路来连接，现在 Mr.Zeng 想找一条旅游路线，这个路线从 A 点出发并且最后回到 A 点，假设经过的路线为 V1，V2，….VK，V1，那么必须满足 K>2，就是说至除了出发点以外至少要经过 2 个其他不同的景区，而且不能重复经过同一个景区。不存在这样的景区 X：从 X 出发不到达其他景区马上回到 X。现在 Mr.Zeng 需要你帮他找一条这样的路线，并且长度越小越好。

输入格式

第一行包含两个正整数：景区个数 N（N<=100），另一个是道路的数目 M（M<10000）。
接下来 M 行每行描述一条路，每一行有三个正整数 A，B，C，其中 A 和 B 分别表示这条路连接的两个景区的编号，C 表示这条路的长度（不超过500的正整数）。

输出格式

如果这条观光路线是不存在的话就显示“No solution.”(有句号)；
如果这条观光路线存在就输出经过的最小长度。

太空飞行计划

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1，E2， $\cdots$ ，Em}，和进行这些实验需要使用的全部仪器的集合 I={I1， I2， $\cdots $In}。 实验 Ej 需要用到的仪器是 I 的子集 Rj∈I。配置仪器 Ik 的费用为 Ck 美元。实验 Ej 的赞助商已同意为该实验结果支付 Pj 美元。W 教授的任务是找出一个有效算法， 确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划，输出最大收益值。

Network of Schools

题目背景

poj1236

题目描述

大致意思: $N(2 < N < 100)$ 各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。

问题：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

传递消息

题目背景

POJ 1125

题目描述

股票经纪人以对传闻的准确判断而闻名。你已签定一个合同，就是研究一种方法，在股票经纪人中间传播假情报，以便雇主在股票市场中赢得先机。为了得到最大效益，你必须尽可能快地散布传闻。

不幸的是，股票经纪人只信任来自他们“可靠来源”的消息。这意味着，在散播传闻时，你必须考虑他们所接触的人际关系。某个股票经纪人需要花一些时间把传闻传递给他的每一位同事。你的任务是写一个程序，确定从哪个证券经纪人开始散播传闻最快，以及传闻传递到整个证券界时所需要最少时间。这个时间是指最后一个人收到传闻的时间。
每个股票经纪人从1开始编号，一直到股票经纪人的总数。