「COCI 2022.4」Naboj 题解

问题分析

核心问题

我们有$n$个金属球（节点）和$m$根导线（边），每条边有一个指定的电子流向（从$b_i$流向$a_i$）。我们需要确定一个给金属球充电的顺序和电荷类型，使得最终所有导线的电子流向满足要求。

关键物理规则分析

从题目描述中可以推导出电荷对电子流向的影响：

1. 正电荷：吸引电子（电子流向该球）
2. 负电荷：排斥电子（电子远离该球）

对于一条边$(a_i, b_i)$，要求电子更靠近$a_i$，这意味着：

• $a_i$应该带正电荷（吸引电子）
• $b_i$应该带负电荷（排斥电子向$a_i$方向）

算法思路

方法一：约束图建模

核心观察：每条边$(a_i, b_i)$给两个节点施加了电荷约束：

• 节点$a_i$必须带正电荷（1）
• 节点$b_i$必须带负电荷（0）

我们可以建立一个约束图，其中：

• 每个节点代表一个金属球
• 每条有向边代表电荷约束关系

方法二：拓扑排序解法

步骤：

1. 构建依赖图：

   • 对于每条输入边$(a_i, b_i)$，我们得到约束：$a_i$必须为正，$b_i$必须为负
   • 如果同一个节点在不同边中被要求带不同的电荷，则出现矛盾，输出-1

2. 检测矛盾：

   • 如果一个节点在某些边中被要求带正电，在另一些边中被要求带负电，则无解
   • 这可以通过检查每个节点的"期望电荷"是否一致来判断

3. 确定充电顺序：

   • 使用拓扑排序确定充电顺序
   • 基本原则：先充那些不会影响后续决策的球

方法三：BFS/DFS遍历

另一种视角：将问题视为在图上传播电荷约束

1. 从任意未确定的节点开始
2. 根据已确定的电荷推断相邻节点的电荷
3. 如果出现矛盾则无解
4. 按照依赖关系确定充电顺序

算法细节

约束传播

对于每条边$(a_i, b_i)$：

• 如果$a_i$已确定电荷：
  • 若$a_i$带负电，则矛盾（因为需要它带正电来吸引电子）
  • 若$a_i$带正电，则$b_i$必须带负电
• 如果$b_i$已确定电荷：
  • 若$b_i$带正电，则矛盾
  • 若$b_i$带负电，则$a_i$必须带正电

充电顺序的确定

关键原则：先充那些电荷类型已经确定的节点

具体策略：

1. 找到所有电荷类型已确定的节点
2. 将这些节点加入队列（作为第一批充电的球）
3. 处理队列中的节点时，检查其邻居：
   • 根据物理规则推断邻居的电荷类型
   • 如果邻居电荷类型确定且无矛盾，加入队列
4. 重复直到所有节点处理完毕

无解的判断条件

出现以下情况时无解：

1. 直接矛盾：同一个节点在不同约束中被要求带相反的电荷
2. 循环依赖：出现电荷约束的循环，无法确定合法的充电顺序
3. 约束冲突：在约束传播过程中发现矛盾

复杂度分析

• 图构建：$O(n + m)$
• 矛盾检测：$O(n)$（检查每个节点的期望电荷一致性）
• 拓扑排序/BFS：$O(n + m)$
• 总体复杂度：$O(n + m)$，可以处理最大数据范围

实现要点

1. 图表示：使用邻接表存储图结构
2. 电荷记录：用数组记录每个节点的期望电荷类型
3. 访问标记：跟踪哪些节点已被处理
4. 队列管理：使用BFS队列确定充电顺序

样例分析

样例1分析

输入边: (1,2), (2,3), (1,3)
约束:
- 边(1,2): 1=正, 2=负
- 边(2,3): 2=正, 3=负  
- 边(1,3): 1=正, 3=负

节点2出现矛盾：既要求为负又要求为正
但通过合适的充电顺序可以解决：
1. 先给2充正电：满足(2,3)
2. 再给3充负电：满足(1,3)和(2,3)
3. 最后给1充正电：满足(1,2)和(1,3)

总结

本题的核心在于将物理问题转化为图论中的约束满足问题。通过分析电荷对电子流向的影响，建立节点间的电荷约束关系，然后使用图遍历算法确定可行的充电序列。

技术亮点：

• 物理规则到图论约束的转化
• 约束传播和矛盾检测
• 基于依赖关系的充电顺序确定
• 高效的图遍历算法应用

这种解法能够在题目给定的大数据范围内高效运行，是处理此类约束满足问题的典型方法。