问题概述

有 $n$ 个小矮人，每个小矮人（除1号和2号外）都希望在自己的照片中站在正中间位置。摄影师带来了 $n$ 顶不同高度的帽子，要求在每张照片中小矮人必须按帽子高度从小到大站好。我们需要判断是否存在满足条件的帽子分配方案。

算法标签

• 拓扑排序
• 图论
• 贪心算法
• 度约束条件

问题分析与建模

关键观察

1. 中间位置约束：对于编号 $i$（$i \geq 3$）的小矮人，在他的照片中，他必须站在正中间位置
2. 朋友数量为偶数：题目保证每个小矮人的朋友数量都是偶数
3. 特殊角色：1号（Gburk）和2号（Wesołek）没有站在中间的要求

图模型建立

将问题转化为图论问题：

• 节点：每个小矮人对应一个节点
• 边：朋友关系构成无向边
• 度数约束：每个节点的度数代表朋友数量

核心思路

对于每个小矮人 $i$（$i \geq 3$），在他的照片中：

• 他站在中间位置
• 左边有 $\frac{deg(i)}{2}$ 个朋友（帽子高度比他小）
• 右边有 $\frac{deg(i)}{2}$ 个朋友（帽子高度比他大）

因此，对于节点 $i$，必须至少有 $\frac{deg(i)}{2}$ 个朋友的帽子编号比他的小。

算法详细步骤

步骤1：输入与初始化

scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &x, &y), g[x].pb(y), g[y].pb(x);
    ++in[x], ++in[y];  // 记录原始度数
}

步骤2：度数处理

// 特殊处理：1号和2号没有站在中间的要求
in[1] = 0;

// 其他小矮人：需要 deg/2 个朋友帽子编号比他小
for (int i = 3; i <= n; ++i)
    in[i] >>= 1;  // 等价于 in[i] = in[i] / 2

解释：

• in[i] 现在表示节点 $i$ 还需要多少个帽子编号比它小的朋友
• 初始时，对于 $i \geq 3$，in[i] = deg(i) / 2
• 对于 $i = 1, 2$，in[i] = 0，表示没有约束

步骤3：拓扑排序预处理

for (int i = 1; i <= n; ++i)
    if (!in[i])  // 度数为0的节点可以立即分配帽子
        q.push(i);

步骤4：拓扑排序过程

while (q.size()) {
    int x = q.front();
    a[x] = ++cnt, q.pop();  // 给节点x分配当前最小的可用帽子编号
    
    for (int y : g[x])  // 遍历x的所有邻居
        if (!a[y]) {    // 如果邻居y还没有分配帽子
            --in[y];    // y的约束减少1（因为x的帽子编号比y小）
            
            if (in[y] < 0)  // 约束过度满足，出现矛盾
                return puts("NIE"), 0;
            
            if (!in[y])     // y的所有约束都已满足
                q.push(y);
        }
}

关键点解释：

• 当给节点 $x$ 分配帽子时，对于它的每个邻居 $y$：
  • 如果 $y$ 还没有分配帽子，那么 $x$ 的帽子编号肯定比 $y$ 小
  • 因此 $y$ 的约束 in[y] 可以减少1
• 如果 in[y] 变为负数，说明有太多帽子编号比 $y$ 小的朋友，这违反了约束条件
• 如果 in[y] 变为0，说明 $y$ 的约束已完全满足，可以分配帽子

步骤5：结果验证与输出

if (cnt < n)  // 还有节点未分配帽子，说明存在环或约束无法满足
    return puts("NIE"), 0;

puts("TAK");
for (int i = 1; i <= n; ++i)
    printf("%d ", a[i]);

算法正确性证明

约束满足性

对于每个节点 $i$（$i \geq 3$）：

• 初始约束：需要 $\frac{deg(i)}{2}$ 个朋友的帽子编号比它小
• 在拓扑排序过程中，只有当约束完全满足（in[i] = 0）时，节点才会被分配帽子
• 因此分配完成后，每个节点都有恰好 $\frac{deg(i)}{2}$ 个朋友的帽子编号比它小

无矛盾性

算法在以下情况会返回"NIE"：

1. 约束过度满足：in[y] < 0，说明有太多帽子编号比 $y$ 小的朋友
2. 循环依赖：cnt < n，说明存在节点无法满足约束，可能由于图中存在不可解的约束环

复杂度分析

时间复杂度

• 图构建：$O(n + m)$
• 拓扑排序：每个节点入队一次，每条边访问一次，$O(n + m)$
• 总时间复杂度：$O(n + m)$

空间复杂度

• 邻接表：$O(n + m)$
• 度数数组和队列：$O(n)$
• 总空间复杂度：$O(n + m)$

样例分析

样例1

输入：6 7
朋友关系：5-6,1-4,4-5,5-3,1-5,3-2,2-6
输出：TAK 1 6 5 2 3 4

验证：

• 节点3：度数为2，需要1个帽子编号比它小的朋友
  • 朋友{2,5}中，节点5的帽子编号(3)比节点3的帽子编号(5)小 ✓
• 节点4：度数为2，需要1个帽子编号比它小的朋友
  • 朋友{1,5}中，节点1的帽子编号(1)比节点4的帽子编号(2)小 ✓
• 节点5：度数为4，需要2个帽子编号比它小的朋友
  • 朋友{1,3,4,6}中，节点1(1)和节点4(2)的帽子编号比节点5(3)小 ✓
• 节点6：度数为3，需要1个帽子编号比它小的朋友
  • 朋友{2,5}中，节点5的帽子编号(3)比节点6的帽子编号(4)小 ✓

总结

本算法通过巧妙的度数约束建模和拓扑排序，高效地解决了小矮人帽子分配问题。算法的核心在于将"站在中间位置"的要求转化为图中节点的度数约束，然后通过拓扑排序来寻找满足所有约束的帽子分配方案。该算法在最优时间复杂度内解决问题，适用于大规模数据输入。