题解:P3561 [POI 2017] Turysta
stripe_python · · 题解
P3561 [POI 2017] Turysta
给出一张
n 个节点的竞赛图,对于每个点u 求出从u 出发的最长简单路径。输出构造。
::::::success[题解]{open}
竞赛图找哈密顿回路练习题。
首先给出如下引理:
-
竞赛图缩 SCC 后形如一条链,每个拓扑序在前的 SCC 都会向在后的 SCC 连边。
-
Landau 定理的推论:记竞赛图中节点
u 的入度为d_u ,将d_u 升序排序,则 SCC 数目为\sum_{k=0}^n \left[\binom{k}{2}=\sum_{i=0}^k d_i\right] 进一步,所有
k 形成了对序列的一个划分,每段都是一个 SCC。 -
Redéi 定理:任何一个竞赛图都至少存在一条哈密顿路。
-
Camion-Moon 定理:强连通竞赛图必然存在哈密顿回路。
前两个定理在这篇 blog 讲的非常详细,这里不证。下面给出后两个定理的构造式证明:
::::success[Redéi 定理]
考虑增量构造。假设我们已经排好了
::::
::::success[Camion-Moon 定理]
先用 Redéi 定理的构造找出一条哈密顿路,然后在路径上顺序扫描。
想象我们当前位于点
我们尝试将
-
若存在
(c_i, x) \in E, (x, c_{i+1}) \in E ,可以直接将x 插入c_i.c_{i+1} 之间。 -
否则,我们向后找到一个点
y ,使得\exists i, (y,c_i) \in E 。将x \to y 的子链插入c_i 之前。根据强连通的定义,必然存在这样的一个
y ,否则后面的点走不到回路上。
::::
我们把这些定理应用到这个问题上。
利用 Landau 定理推论找出所有 SCC 并缩点后,DAG 的形态类似一条链。
考虑找出每个 SCC 的哈密顿回路。根据 DAG 的形态,直接取一段后缀的哈密顿回路拼起来,就能构成一条简单路径。
这样,这个问题的做法就显然了:利用 Camion-Moon 定理的构造求得 SCC 的哈密顿回路。对于一点
精细实现复杂度
::::::
:::::info[代码]
const int N = 2005;
int n, m, d[N], p[N], bel[N];
vector<int> e[N], scc[N], hp[N];
bitset<N> has[N];
void work(int id) {
vector<int> P, C;
auto redei = [&]() -> void {
for (int u : scc[id]) {
int s = P.size();
for (auto it = P.begin(); it != P.end(); it++)
if (has[u][*it]) {
P.insert(it, u); break;
}
if ((int)P.size() == s) P.emplace_back(u);
}
};
auto camion = [&]() -> void {
C.emplace_back(P[0]);
int i = 1, n = P.size();
while (i < n) {
int c = C.size(), to = -1, u = P[i];
for (int j = 0; j < c; j++)
if (has[u][C[j]]) {
to = j; break;
}
if (to != -1) {
int p = 0;
for (int j = 0; j < c; j++) {
int k = (j + 1) % c;
if (has[C[j]][u] && has[u][C[k]]) {
p = k; break;
}
}
if (p == 0) C.emplace_back(u);
else C.insert(C.begin() + p, u);
i++;
} else {
int j = i + 1, p = -1;
for (; j < n && p == -1; j++)
for (int k = 0; k < c; k++)
if (has[P[j]][C[k]]) {
p = k; break;
}
if (p == 0) C.insert(C.end(), P.begin() + i, P.begin() + j);
else C.insert(C.begin() + p, P.begin() + i, P.begin() + j);
i = j;
}
}
};
redei(), camion(), hp[id].swap(C);
}
void _main() {
cin >> n;
for (int u = 2; u <= n; u++)
for (int v = 1, x; v < u; v++) {
cin >> x;
if (x) e[v].emplace_back(u), has[v][u] = 1, d[u]++;
else e[u].emplace_back(v), has[u][v] = 1, d[v]++;
}
iota(p + 1, p + n + 1, 1), sort(p + 1, p + n + 1, [](int u, int v) -> bool {
return d[u] < d[v];
});
for (int i = 1, sum = 0, last = 0; i <= n; i++) {
sum += d[p[i]];
if (sum == i * (i - 1) / 2) {
scc[++m] = vector<int>(p + last + 1, p + i + 1);
for (int j = last + 1; j <= i; j++) bel[p[j]] = m;
last = i;
}
}
for (int i = 1; i <= m; i++) work(i);
for (int u = 1; u <= n; u++) {
vector<int> vec = hp[bel[u]];
rotate(vec.begin(), find(vec.begin(), vec.end(), u), vec.end());
for (int i = bel[u] + 1; i <= m; i++)
vec.insert(vec.end(), hp[i].begin(), hp[i].end());
cout << vec.size() << ' ';
for (int v : vec) cout << v << ' ';
cout << '\n';
}
}
:::::