Входной файл: | 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 |
|
|