Есть поле n×n, которое нужно полить удобрениями. Это можно делать тремя способами: можно полить одну клетку (i, j), это будет стоить ci,j , можно полить целиком горизонталь i, это будет стоить ri, можно целиком вертикаль j, это будет стоить cj. Нужно полить все клетки хотя бы по одному разу, минимизировав суммарную стоимость.
В наивном представлении сеть s->(cost)->aij->t (где cost состоит из цен ri, ci, pij) (pij цена для единичной клетки, ri- ряд, ci - колонка) как-то дело не идёт.
Было 3 варианта куда думать:
1) как-то сделать, чтобы разрезы между cost и aij были такими, что все конфигурации, где каждая клетка не помечена хотя бы раз запрещены, тогда магическим образом нужное разбинение должно было бы найтись само
2) использовать факт, что в каждую клетку aij входит не более чем max(pij, ri/n + cj/n) ну и ещё можно добавить ограничение, что пусть разрез равен x.
3) как-то преобразовать веса в сети s->(cost)->aij->t
Вам нужен 2-дольный граф. Левая доля соответствует строкам, правая - столбцам. Из истока ребора в левую долю (ценой ri), из правой доли - в сток (ценой ci). Ребра между долями ценой aij.
Любой разрез тут соответствует покрытию всех вершин. Вы должны разрезать ребро между ij или si или jt что чоответствует покрытию клетки, строки иои столбца.
Средний
Простой
