Задача F. (20081222) Разрезы

Автор:Илья Разенштейн   Ограничение времени: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
6 6
1 2 1
2 3 2
2 4 3
3 5 3
4 5 2
5 6 1
16
011111
000001
011001
011101
010101
010001
011011
001001
000101
001011
010111
001111
000011
010011
000111
001101

0.135s 0.014s 13