5 月训练记录

[POI2017]Turysta

学习了竞赛图构造汉密尔顿回路。

首先对竞赛图缩点，最终拓扑序一定是一条链。考虑如何在一个强连通竞赛图中构造汉密尔顿回路。

首先，我们尝试构造汉密尔顿通路。考虑增量构造。我们一个个地加点，设当前加入的点为 \(x\)，当前构造好的路径为 \(s\) 到 \(t\)，那么我们分类讨论：

1. 若 \(x\to s\)，我们直接让 \(x\) 连接 \(s\)，\(s:=x\)；
2. 若 \(t\to x\)，我们直接让 \(t\) 连接 \(x\)，\(t:=x\)；
3. 现在我们只剩下 \(s\to x\)，\(x\to t\) 的情况，于是考虑链上一定存在一个点 \(y\) 以及 \(y\) 连接的点 \(z\)，满足 \(y\to x\)，\(x\to z\)。于是直接在 \(y\to z\) 中插入 \(x\) 即可。

考虑多次进行这个过程，每次对点 shuffle，即可获得 \(98\) 分，当然这样确实是可以卡的。

接着我们考虑构造汉密尔顿通路。我们依旧考虑增量构造（但不是纯增量构造）。设当前加入的点为 \(x\)，当前构造好的环起点为 \(s\)，我们依旧分类讨论：

1. 若 \(x\to s\)，那么我们直接按照汉密尔顿通路并加入 \(x\to s\) 的边即可；
2. 若存在点 \(x\to y\)，\(y\) 在已经构造好的环中，我们找到从 \(s\) 开始往后第一个这样的点，设环中 \(z\to y\)。由于我们找的是第一个，并且 \(s\to x\)，所以，一定有 \(z \to x\)。于是就可以构造了。
3. 若不存在情况 2，则我们把这个点留下，并在之后一起构造。

情况 2、3 的构造：

时间复杂度 \(O(n^2)\)。

记录。