Дан ориентированный ацикличный граф (ориентированный граф, не содержащий циклов) из $$$n$$$ вершин и $$$m$$$ дуг. $$$i$$$-я дуга ведет из вершины $$$x_i$$$ в вершину $$$y_i$$$ и имеет вес $$$w_i$$$.
Ваша задача — для каждой вершины $$$v$$$ выбрать некоторое целое число $$$a_v$$$, после чего на каждой дуге $$$i$$$ записать такое число $$$b_i$$$, что $$$b_i = a_{x_i} - a_{y_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$$$.
3 2 2 1 4 1 3 2
1 2 0
5 4 1 2 1 2 3 1 1 3 6 4 5 8
43 42 41 1337 1336
5 5 1 2 1 2 3 1 3 4 1 1 5 1 5 4 10
4 3 2 1 2
Название |
---|