#P3687. Labeling Balls
Labeling Balls
题目翻译(P3687. 球的重标号)
标签:图论、拓扑排序
题目描述
Windy 有 个重量互不相同的球,重量分别为 单位到 单位。现在,他需要将这些球重新标号为 到 ,并满足以下条件:
- 标号唯一性:任意两个球的标号不能相同。
- 约束条件:存在若干形如 “标号为 的球必须比标号为 的球轻” 的约束(即 )。
请帮助 Windy 找出满足条件的标号方案。
输入格式
- 第一行为测试用例的数量 。
- 每个测试用例的第一行包含两个整数 ()和 (),分别表示球的数量和约束条件的数量。
- 接下来的 行,每行包含两个整数 和 ,表示标号为 的球必须比标号为 的球轻()。
- 注意:每个测试用例前有一个空行。
输出格式
对于每个测试用例,输出一行:
- 如果存在合法标号方案,输出标号 到 对应的球的重量(用空格分隔)。
- 多解时:优先保证标号 的重量最小,其次标号 的重量最小,依此类推(即字典序最小解)。
- 如果无解,输出 。
样例输入
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
关键点说明
-
问题本质:
- 将 个球的重量( 到 )映射到标号 到 ,满足 个约束 。
- 等价于拓扑排序问题,需检查图中是否有环(无解)并输出字典序最小的拓扑序。
-
字典序最小解:
- 使用优先队列(最小堆)实现拓扑排序,每次选择当前可分配的最小重量。
-
特殊约束:
- 若出现 的约束(如样例第二组),直接判定无解()。
- 若约束形成环(如样例第三组),同样无解。