# 一种最大流数据生成方法

$1198$ 个点，$120796$ 条边运行时间均超过 $1 \mathrm{min}$（当然也可能是我的最大流写得太菜）

# 「BJ模拟」「CF-Gym101190B」Binary Code-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′ 替换那些看不清的字符，使得这条信息变为漂亮的二进制信息。

# 「HDU-1116」Play on Words-欧拉回路

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.

# 「POJ-3678」Katu Puzzle-2-SAT

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

# 「POJ-3648」Wedding-2-SAT

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.

# 「POJ-2942」Knights of the Round Table-点双连通分量+奇环判定

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.

# 「POJ-3180」The Cow Prom-tarjan

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.

# 「POJ-1523」SPF-割点

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.

# 「UOJ-117」欧拉回路

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

# SPFA-SLF优化

## SPFA【SLF优化】

### SLF

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

# 「SuperOJ 381」最佳路线

## 最佳路线

### 题目描述

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

# 「SuperOJ 430」太空飞行计划

## 太空飞行计划

### 题目描述

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

poj1236

POJ 1125