← 返回题目列表

Codeforces · 1430/G

G. 又一个 DAG 问题

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 个顶点和 $$$m$$$ 弧组成的有向无环图(不包含循环的有向图)。第 $$$i$$$ 弧从顶点 $$$x_i$$$ 引向顶点 $$$y_i$$$,权重为 $$$w_i$$$。

你的任务是为每个顶点 $$$v$$$ 选择一个整数 $$$a_v$$$,然后在每个弧 $$$i$$$ 上写入一个数字 $$$b_i$$$,使得 $$$b_i = a_{x_i} - a_{y_i}$$$。您必须选择数字以便:

- 所有 $$$b_i$$$ 均为正;
- 表达式 $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ 的值是可能的最低值。

可以证明,对于任何具有非负$$$w_i$$$的有向无环图,存在这样的选择数字的方法。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 18$$$; $$$0 \le m \le \dfrac{n(n - 1)}{2}$$$)。

接下来是 $$$m$$$ 行,其中第 $$$i$$$ 包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$1 \le w_i \le 10^5$$$, $$$x_i \ne y_i$$$) — 第 $$$i$$$ 条弧的描述。

保证这些线描述了有向无环图的 $$$m$$$ 弧,在同一对顶点之间没有多个弧。

输出

打印 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_v \le 10^9$$$),必须写在顶点上,以便所有 $$$b_i$$$ 均为正数,并且表达式 $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ 是可能的最低值。如果有多个答案,请打印其中任何一个。可以证明答案总是存在的,并且至少有一个最优答案满足约束$$$0 \le a_v \le 10^9$$$。

示例

输入 #1

3 2
2 1 4
1 3 2

输出 #1

1 2 0

输入 #2

5 4
1 2 1
2 3 1
1 3 6
4 5 8

输出 #2

43 42 41 1337 1336

输入 #3

5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10

输出 #3

4 3 2 1 2