Page 168 - Bkhargava_-_Grokaem_algoritmy

Ребра с отрицательным весом 167

Ребра с отрицательным весом ПЛАСТИНКА

В предыдущем примере Алекс предложил в обмен
на книгу один из двух предметов.
Предположим, Сара предложила обменять пла­
стинку на постер и при этом она еще и даст Раме
$7. Рама ничего не тратит при этом обмене, вместо
этого он получит $7. Как изобразить это предло­ ПОСТЕР
жение на графе?

ПЛАСТИНКА
(АРА дАС.Т РАМЕ.
.,/ .Ы, ЕС.ЛИ ОН
1 ПOME.HJIET С.&ОЮ
книrА il ПЛАСТИНКУ
НА Е.Е ПОСТЕР

ПОС.ТЕР

Ребро, ведущее от пластинки к постеру, имеет отрицательный вес! Если
Рама пойдет на этот обмен, он получит $7. Теперь к постеру можно до­
браться двумя способами.

ПЛАСТИНКА ПЛАСТИНКА

КНИГА КНИГА

ПОС.ПР ПОСТЕР
ее.ли РАМА ИДЕТ ЕСЛИ РАМА ИдЕ.Т
ПО ЭТОМУ ПУТИ,
ПО ЭТОМУ ПУТИ,
ОН ПОЛУЧАЕТ .t.O
ОН ПОЛУЧАЕТ .t.2.

www.trk.kg