Автор: | Илья Разенштейн | Ограничение времени: | 2 сек | |
Входной файл: | cuts.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | cuts.out | |||
Максимальный балл: | 100 |
Рассмотрим ориентированный взвешенный граф G = (V,E) с двумя выделенными вершинами s и t. Веса всех ребер — натуральные числа. Назовем s − t разрезом пару множеств вершин S и T такую, что выполняются следующие условия:
Назовем величиной разреза (S,T) суммарный вес ребер, которые направлены из S в T. Упорядочим все s − t разрезы G по неубыванию величины. Вам нужно вывести первые k разрезов в этом порядке.
В первой строке записаны два натуральных числа n и m — количество вершин и ребер в графе (1 ≤ n ≤ 50, 1 ≤ m ≤ 300). В следующих m строках находятся описания ребер — три натуральных числа a, b и c, которые задают ребро, идущее из вершины a в вершину b с весом c (1 ≤ a, b ≤ n, 1 ≤ c ≤ 109). Гарантируется, что в графе нет кратных ребер и петель (однако могут быть два ребра, направленные друг навстречу другу). Последняя строка содержит одно натуральное число k — количество разрезов, которые необходимо вывести (1 ≤ k ≤ 300, k не превосходит общее количество разрезов в графе).
Вершины s и t имеют номера 1 и n соответственно.
Выведите искомые k разрезов по одному на строке. Разрез задается строкой, состоящей из n символов. i-й символ равен нулю, если вершина с номером i лежит в S, в противном случае i-й символ должен равняться единице. Если несколько разрезов имеют одинаковую величину, то вы можете вывести их в любом порядке.
№ | Входной файл (cuts.in ) |
Выходной файл (cuts.out ) |
---|---|---|
1 |
|
|