Максимальный покрывающий лес орграфа
Максимальный покрывающий лес орграфа
Задан ориентированный взвешенный граф. Требуется покрыть его набором исходящих деревьев суммарной максимальной стоимости, которые непересекаются по вершинам.
Giriş verilənləri
Входной файл состоит из одного или более наборов входных данных. Каждый набор начинается со строки, содержащей два целых числа n и m (1 ≤ n ≤ 200, 0 ≤ m ≤ 10000). n - количество вершин графа, а m - количество рёбер. Далее идёт m строк, каждая из которых содержит по три числа x_i, y_i, c_i - стартовую вершину, конечную вершину и вес дуги. Орграф не содержит петель, но может содержать кратные дуги.
Суммарное количество дуг по всем наборам входных данных одного теста не превосходит 10000.
Çıxış verilənləri
Для каждого набора входных данных выведите три строки. В первую из них выведите вес оптимального покрытия деревьями, во вторую - количество дуг в покрытии, в третью - номера выбранных в покрытие дуг. Выведите пустую строку после каждого блока выходных данных.
Nümunə
6 8 6 1 7 5 6 2 3 6 5 1 2 5 4 5 4 3 4 6 3 1 8 6 3 1 6 8 4 5 1 6 2 4 6 1 6 2 3 7 3 2 7 1 6 8 2 5 6 5 1 4
28 5 3 4 5 6 7 25 4 2 4 6 7