1302
правки
Изменения
→1 | intree | Sum(w_i C_i)
=== Примеры ===
==== 1 | intree | Sum(w_i C_i) ====
Предположим, что мы уже умеем решать [[1outtreesumwc|задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex>]]<ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 73 </ref>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
