AT_abc352_f [ABC352F] Estimate Order

题目描述

有 $N$ 个人，每个人分别被编号为 $1, 2, \ldots, N$。

这 $N$ 个人进行了一场比赛，并得到了名次。关于这些名次，给出了如下信息：

• 每个人被分配的名次互不相同。
• 对于每个 $1 \leq i \leq M$，设第 $A_i$ 个人的名次为 $x$，第 $B_i$ 个人的名次为 $y$，则有 $x - y = C_i$。

此外，本题保证输入的数据不会出现矛盾，即至少存在一种满足所有条件的名次分配方式。

请你回答 $N$ 个查询。对于第 $i$ 个查询，答案定义如下：

• 如果第 $i$ 个人的名次可以唯一确定，则输出该名次。
• 否则，输出 $-1$。

输入格式

输入从标准输入中读取，格式如下：

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\cdots$ $A_M$ $B_M$ $C_M$

输出格式

请按顺序输出第 $1, 2, \ldots, N$ 个查询的答案，使用空格分隔。

输入输出样例 #1

输入 #1

5 2
2 3 3
5 4 3

输出 #1

3 -1 -1 -1 -1

输入输出样例 #2

输入 #2

3 0

输出 #2

-1 -1 -1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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)$
• 输入保证至少存在一种满足所有条件的名次分配方式
• 所有输入的值均为整数

样例解释 1

设第 $i$ 个人的名次为 $X_i$，则 $(X_1, X_2, X_3, X_4, X_5)$ 可能为 $(3, 4, 1, 2, 5)$ 或 $(3, 5, 2, 1, 4)$。因此，第 $1$ 个查询的答案为 $3$，第 $2, 3, 4, 5$ 个查询的答案均为 $-1$。

由 ChatGPT 4.1 翻译