Входной файл: | input.txt | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 64 Мб |
Требуется найти максимальный поток в сети с несколькими истоками и стоками.
В первой строке входного файла содержится число N — количество вершин в сети. Далее следует N чисел ai ∈ 0, 1, 2. Если ai = 0, то i-ая вершина — это обычный узел; если ai = 1 то i-ая вершина — это исток; если ai = 2 то i-ая вершина — это сток. Гарантируется, что в сети есть хотя бы один исток и хотя бы один сток.
Далее следует матрица целых чисел U размером N × N. 0 ≤ Uij ≤ 106 — вместимость ребра из i-ой вершины в j-ую. На диагонали матрицы находятся нули.
В выходной файл выведите единственное число — объем максимального потока.
2 ≤ N ≤ 50
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|