#P3687. Labeling Balls

    ID: 2688 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>图结构其他排序POJ Founder Monthly Contest – 2008.08.31windy7926778

Labeling Balls

题目翻译(P3687. 球的重标号)

标签:图论、拓扑排序


题目描述

Windy 有 NN 个重量互不相同的球,重量分别为 11 单位到 NN 单位。现在,他需要将这些球重新标号为 11NN,并满足以下条件:

  1. 标号唯一性:任意两个球的标号不能相同。
  2. 约束条件:存在若干形如 “标号为 aa 的球必须比标号为 bb 的球轻” 的约束(即 a<ba < b)。

请帮助 Windy 找出满足条件的标号方案。

输入格式

  • 第一行为测试用例的数量 TT
  • 每个测试用例的第一行包含两个整数 NN1N2001 \leq N \leq 200)和 MM0M40,0000 \leq M \leq 40,000),分别表示球的数量和约束条件的数量。
  • 接下来的 MM 行,每行包含两个整数 aabb,表示标号为 aa 的球必须比标号为 bb 的球轻(1a,bN1 \leq a, b \leq N)。
  • 注意:每个测试用例前有一个空行。

输出格式

对于每个测试用例,输出一行:

  • 如果存在合法标号方案,输出标号 11NN 对应的球的重量(用空格分隔)。
    • 多解时:优先保证标号 11 的重量最小,其次标号 22 的重量最小,依此类推(即字典序最小解)。
  • 如果无解,输出 1-1

样例输入

5

4 0

4 1
1 1

4 2
1 2
2 1

4 1
2 1

4 1
3 2

样例输出

1 2 3 4
-1
-1
2 1 3 4
1 3 2 4

题目来源

POJ Founder Monthly Contest – 2008.08.31, windy7926778


关键点说明

  1. 问题本质

    • NN 个球的重量11NN)映射到标号 11NN,满足 MM 个约束 a<ba < b
    • 等价于拓扑排序问题,需检查图中是否有环(无解)并输出字典序最小的拓扑序。
  2. 字典序最小解

    • 使用优先队列(最小堆)实现拓扑排序,每次选择当前可分配的最小重量。
  3. 特殊约束

    • 若出现 a=ba = b 的约束(如样例第二组),直接判定无解(1-1)。
    • 若约束形成环(如样例第三组),同样无解。