分数: 525 点
问题陈述
有 N 人,已编号 1 to N.
在这些人之间举行了一场比赛 N 人,并且他们被相应地排名。以下是有关他们的排名的信息:
- 每个人都有一个独特的等级。
- 对于每个 1 \leq i \leq M,如果人 A_i 排名 x-th 和人 B_i 排名 y-th,然后 x - y = C_i.
给定的输入保证至少有一个可能的排名与给定的信息不矛盾。
答案 N 查询。答案是 i-第一个查询是一个整数,确定如下:
- 如果人的等级 i 可以唯一确定,返回该排名。否则,返回 -1.
约束
- 2 \leq N \leq 16
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq A_i, B_i \leq N
- 1 \leq C_i \leq N - 1
- (A_i, B_i) \neq (A_j, B_j) (i \neq j)
- 至少有一种可能的排名与给定信息不矛盾。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
输出
打印以下问题的答案 1-st, 2-nd, \ldots, N- 按此顺序查询,以空格分隔。
示例输入 1
5 2 2 3 3 5 4 3
示例输出 1
3 -1 -1 -1 -1
让 X_i 是人的等级 i。然后, (X_1, X_2, X_3, X_4, X_5) 可能是 (3, 4, 1, 2, 5) or (3, 5, 2, 1, 4).
因此,答案 1-st 查询是 3,以及问题的答案 2-nd, 3-rd, 选择 4-th,以及 5-第查询是 -1.
示例输入 2
3 0
示例输出 2
-1 -1 -1
示例输入 3
8 5 6 7 3 8 1 7 4 5 1 7 2 1 6 2 4
示例输出 3
1 -1 -1 -1 -1 -1 -1 8