AGC028C Min Cost Cycle

发表于 2025-02-20 更新于 2025-02-26 分类于算法竞赛，题， AtCoder 阅读次数：

题意：给出一张个点的有向图，其中点有点权。

对于，边的权值为。

求图的最短哈密顿环。

，时限。

处理最优化问题的一类巧妙手段：

有时只是灵机一动减少细节，有时则成为解题的关键。

如何简化约束？难点有两方面，一是“简化”只能产生更差的冗余解；二是“简化”要足够强，足以使得我们能得到好做法。

一般来说，第一点比较直接，通过分析问题本身的性质就能处理；第二点则比较迂回，要通过题目中的碎片信息，以及经验，猜想出转化后的形式。

本题题意较为简单，于是先从题目条件入手。

对于每个，只有“贡献”或“不贡献”两种可能。且最终一共有个数贡献了。

对于一个给定的有贡献的集合，考虑如何判定一个给定的哈密顿环是否合法。

一个显然的必要条件是：对于每条边，均满足恰有一个在中。

若只考虑这个条件，会产生冗余的解（即在某条边处选了较大值而非较小值），但不难证明这些解都是不优的。

接下来考虑如何判定一个给定的是否存在一种对应的哈密顿环。

将个点分为如下四类：

首先可以将所有的 10， 01 分别首尾相连，形成两条可以看做单个 10 或 01 的链。

若全为 10 或全为 01，则可以直接形成一个大环。

若存在 00 与 11，由不难证明两者个数相同。

若没有 10 和 01，构造 00 + 11 + 00 + 11 （交替）。

若有 10 和 01，构造 10 + 11 + 01 + 00 + 11 + 00 + 11（交替）。

只剩下一种情况：不存在 00 和 11 （每对恰被选中一个），且为 10 和 01 混杂。此时 10 和 01 之间无法连边，无解。

得到了合法的充要条件，我们先来尝试考虑一些特殊方案（答案的下界）。

将混合排序（记结果为），取前小的作为。若合法，则显然是最优解。

若不合法，则将换成，若合法，则显然是最优解。

若仍然不合法，则说明分别为某点的。

此时考虑将换成（导致同时不选），或者将换成（导致同时选），不难发现这两个方案都必然合法，取最小值即可。

复杂度。

总结：考察了最优化问题中“映射转化”、“冗余解集”两类经典技巧，且最终解法非常简洁，好题。