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

Нечётный разрез

Нечётный разрез

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

Задан связный неориентированный граф из n вершин и m рёбер. Рёбрам приписаны неотрицательные целые веса. Известно, что n чётное. Найдите разбиение множества вершин на множества A и B такое, чтобы выполнялись следующие условия:

  1. A

    B =

    ,

  2. |A| и |B| - нечётные числа,

  3. суммарный вес рёбер, один конец которых находится в A, а другой - в B, минимален.

Giriş verilənləri

В первой строке находится два числа - n и m (1n200, 1m2000). В следующих m строках находятся описания рёбер графа. Каждая из них содержит номера концов ребра и его вес - целое число от 0 до 10^5, включительно. Вершины графа нумеруются с единицы. Гарантируется, что в графе нет петель, хотя могут быть кратные рёбра.

Çıxış verilənləri

Выведите в первой строке искомый минимальный вес рёбер.

Во второй строке выведите размер множества A.

В третьей строке выведите номера вершин, которые входят в это множество.

Nümunə

Giriş verilənləri #1
6 9
6 1 1
6 2 7
2 1 1
1 4 2
2 4 4
1 3 3
3 4 1
3 5 6
4 5 2
Çıxış verilənləri #1
7
3
1 3 5
Müəllif I.Razenshteyn, V.Goldshteyn