题目概述

题目「旅行商问题」是 CCO 2020 Day2 的 T1 题，要求我们在一个完全图中设计路径，使得：

1. 路径覆盖所有节点：每条路径必须经过所有建筑至少一次。
2. 颜色切换次数 ≤ 1：路径中相邻边的颜色切换次数不能超过 1。
3. 最小化路径长度：在满足前两个条件的情况下，尽可能减少重复访问的建筑数。

输入与输出

• 输入：

  • 第一行给出建筑数量 $N$。
  • 接下来的 $N-1$ 行给出边颜色信息，$C_{i,j}$ 表示建筑 $i$ 和 $j$ 之间的边颜色（R 或 B）。

• 输出：

  • 对于每个建筑 $i$，输出两行：
    1. 路径长度 $M_i$。
    2. 路径的具体节点序列，起点必须是 $i$。

解题思路

本题的关键在于构造路径时，颜色切换次数不超过 1，同时尽可能减少路径长度。由于颜色切换次数限制严格，我们需要找到一种高效的遍历方式，使得路径在遍历所有建筑时尽可能少地改变颜色。

核心观察

1. 颜色切换 ≤ 1：

   • 这意味着路径的颜色最多只能变化一次（如从 R 切换到 B 或反之）。
   • 因此，路径可以分成两部分：
     • 第一部分：所有边颜色相同（例如全部 R）。
     • 第二部分：所有边颜色相同（例如全部 B）。
   • 切换点只能有一个。

2. 最小化路径长度：

   • 由于需要覆盖所有建筑，最优路径长度通常是 $N$（即不重复访问任何建筑）。
   • 但如果颜色限制导致无法直接遍历所有建筑而不切换颜色，则需要适当重复访问某些建筑。

算法思路

1. 贪心构造路径：

   • 对于每个起点 $i$，尝试构造一条路径，使得颜色切换不超过 1 次。
   • 可以采用类似链式遍历的方法，动态维护当前路径的颜色状态，并在必要时插入节点以保持颜色一致性。

2. 链表维护路径：

   • 使用双向链表（pre 和 nxt 数组）动态维护当前路径。
   • 遍历所有建筑，尝试将新建筑插入到当前路径的合适位置，使得颜色切换次数最小。

3. 颜色一致性检查：

   • 在插入新节点时，检查其与相邻节点的边颜色是否一致。
   • 如果不一致，可能需要调整插入位置或允许一次颜色切换。

代码分析（伪代码逻辑）

1. 输入处理：

   • 读取 $N$ 和颜色矩阵 $col$。

2. 路径构造：

   • 对于每个起点 $i$：
     • 初始化链表结构（pre 和 nxt 数组）。
     • 遍历所有建筑 $j$（$j \neq i$），尝试将其插入当前路径：
       • 如果当前路径为空，直接插入。
       • 否则，检查插入位置的颜色一致性：
         • 如果颜色一致，直接插入。
         • 如果不一致，尝试在另一侧插入或调整路径。
     • 最终输出路径长度和节点序列。

3. 输出优化：

   • 确保路径长度不超过 $2K_i$（$K_i$ 是最优路径长度），否则会得 0 分。

示例解释

以样例输入为例：

4
R
RR
BRB

• 建筑之间的边颜色：
  • 1-2: R
  • 1-3: R
  • 1-4: B
  • 2-3: R
  • 2-4: R
  • 3-4: B

对于起点 $3$，最优路径是 $3 \rightarrow 2 \rightarrow 1 \rightarrow 4$：

• 边颜色：$3-2$（R），$2-1$（R），$1-4$（B）。
• 颜色切换次数：1（从 R 切换到 B）。
• 路径长度：4（最优）。

得分机制

• 如果所有 $M_i = K_i$（最优），得 100 分。
• 否则，得分按公式计算：$$\min_{1 \leq i \leq N} \left\{ 4 \times \left\lfloor 8 + 8 \times \frac{K_i - 1}{2K_i - M_i} \right\rfloor \right\}. $$
• 如果任何路径不合法（颜色切换 > 1 或 $M_i > 2K_i$），直接得 0 分。

总结

本题的关键在于如何在颜色切换限制下高效遍历所有建筑。通过贪心插入和链表维护，可以构造出满足条件的路径。需要注意颜色一致性和路径长度的优化，以确保得分最大化。