Задан ориентированный граф, каждое ребро которого обладает целочисленной пропускной способностью. Найдите максимальный поток из вершины с номером 1 в вершину с номером n.
Первая строка входного файла содержит n и m — количество вершин и количество ребер графа (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Следующие m строк содержат по три числа: номера вершин, которые соединяет соответствующее ребро графа и его пропускную способность. Пропускные способности не превосходят 105.
В выходной файл выведите одно число — величину максимального потока из вершины с номером 1 в вершину с номером n.
4 5
1 2 1
1 3 2
3 2 1
2 4 2
3 4 1
3
Задан ориентированный граф, каждое ребро которого обладает целочисленной пропускной способностью. Найдите максимальный поток из вершины с номером 1 в вершину с номером n.
Первая строка входного файла содержит n и m — число вершин и ребер в графе (2 ≤ n ≤ 500, 1 ≤ m ≤ 10 000). Последующие строки описывают ребра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности не превосходят 109.
Выведите величину максимального потока между вершинами 1 и n.
4 5
1 2 1
1 3 2
3 2 1
2 4 2
3 4 1
3
Задан ориентированный граф, каждое ребро которого обладает целочисленной пропускной способностью. Найдите максимальный поток из вершины с номером 1 в вершину с номером n и постройте декомпозицию этого потока.
Первая строка входного файла содержит n и m — количество вершин и количество ребер графа (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000). Следующие m строк содержат по три числа: номера вершин, которые соединяет соответствующее ребро графа и его пропускную способность. Пропускные способности не превосходят 109.
В первую строку выходного файла выведите одно число — количество путей в декомпозции максимального потока из вершины с номером 1 в вершину с номером n. Следующий строки должны содержать описания элементарых потоков, на который был разбит максимальный. Описание следует выводить в следующем формате: величина потока, количество ребер в пути, вдоль которого течет данный поток и номера ребер в этом пути. Ребра нумеруются с единицы в порядке появления во входном файле.
4 5
1 2 1
1 3 2
3 2 1
2 4 2
3 4 1
3
1 2 1 4
1 3 2 3 4
1 2 2 5
В Университете города М. проводят эксперимент. Преподаватели сами решают, что они будут читать в рамках того или иного курса. И вот преподаватель математического анализа (в простонародье — матана) оценил по некоторым критериям все известные ему темы в данном курсе. В результате этой ревизии каждой теме сопоставлено некоторое целое число (возможно, отрицательное) — полезность данной темы. Профессор хочет максимизировать суммарную полезность прочитанных им тем, но не все так просто. Для того что бы студенты поняли некоторые темы, необходимо, чтобы были прочитаны так же некоторые другие темы, так как некоторые доказательства базируются на фактах из других тем. Однако если существует цикл из зависимостей тем, то их все можно прочитать, и на качестве понимания материала студентами это не скажется.
Вас попросили составить список тем, которые профессор должен прочитать, таким образом, чтобы студенты все поняли, и суммарная полезность курса была максимальна.
Первая строка входного файла содержит одно число — N (1 ≤ N ≤ 200). Вторая строка содержит N целых чисел, не превосходящих по модулю 1 000 — полезности каждой темы. Далее следуют N строк с описанием зависимостей тем. Каждое описание начинается количеством тем, которые необходимо понять для понимания данной темы. Потом следуют номера этих тем, разделенные пробелами.
Выведите единственное число — максимально возможную суммарную полезность прочитанного материала.
4
-1 1 -2 2
0
1 1
2 4 2
1 1
2
3
2 -1 -2
2 2 3
0
0
0