|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 19-1. Симпатичные таблицы.
(Разбор)
Во первых, если вычесть уже расставленные числа из ограничений на сумму чисел в соответствующих строках и столбцах, то задача сведется к аналогичной. Ответ будет различаться ровно на эти числа. Значит, далее будем считать, что все изначально расставленные числа равны 0.
Построим сеть из N+M+2 вершин. Вершинами будут строки матрицы, ее столбцы и две дополнительные вершины: исток и сток. Из истока будут вести дуги в вершины, соотвествующие строкам с пропускной способностью Ri. Из вершин, соответствующих столбцам, будут идти дуги в сток с пропускной способностью Cj. Вершины, соответствующие i-й строке и j-му столбцу будут соединены дугой тогда и только тогда, когда на пересечении i-й строки и j-го столбца в оригинальной матрице стояло число -1. Пропускная способность таких дуг будет равна бесконечности. Максимальный поток в этой сети и будет ответом на поставленную задачу.
Сеть можно не строить явно, а продолжать работать с матрицей.