Изменения

== Определение задачи ==

Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества [[Определение сети, потока|потока]] через заданную [[Определение сети, потока|сеть]].

{{Определение

|definition=Дано число <tex>f_0</tex> и транспортная сеть <tex>\,G(V,E)</tex> с источником <tex>s \in V</tex> и стоком <tex>t \in V</tex>, где ребра <tex>(u,v) \in E</tex> имеют пропускную способность <tex>\,c(u,v)</tex> и цену <tex>\,p(u,v)</tex>.

* Дана квадратная матрица <tex>A_{N\times N}</tex>. Нужно выбрать в ней <tex>N</tex> элементов так, чтобы в каждой строке и в каждом столбце был выбран только один элемент, а сумма значений этих элементов была наименьшей.

* Имеется <tex>N</tex> заказов и <tex>N</tex> станков. Про каждый заказ известна стоимость его изготовления на каждом станке. На каждом станке можно выполнять только один заказ. Требуется распределить все заказы по станкам так, чтобы минимизировать суммарную стоимость.

== Источник ==