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)$ 各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。

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