eolymp
bolt
Try our new interface for solving problems
Məsələlər

Максимальный покрывающий лес орграфа

Максимальный покрывающий лес орграфа

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Задан ориентированный взвешенный граф. Требуется покрыть его набором исходящих деревьев суммарной максимальной стоимости, которые непересекаются по вершинам.

Giriş verilənləri

Входной файл состоит из одного или более наборов входных данных. Каждый набор начинается со строки, содержащей два целых числа n и m (1n200, 0m10000). n - количество вершин графа, а m - количество рёбер. Далее идёт m строк, каждая из которых содержит по три числа x_i, y_i, c_i - стартовую вершину, конечную вершину и вес дуги. Орграф не содержит петель, но может содержать кратные дуги.

Суммарное количество дуг по всем наборам входных данных одного теста не превосходит 10000.

Çıxış verilənləri

Для каждого набора входных данных выведите три строки. В первую из них выведите вес оптимального покрытия деревьями, во вторую - количество дуг в покрытии, в третью - номера выбранных в покрытие дуг. Выведите пустую строку после каждого блока выходных данных.

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
28
5
3 4 5 6 7 

25
4
2 4 6 7