|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 07-3. Флойд - существование
(Разбор)
Применим алгоритм Флойда...
В этой задаче есть ряд подводных камней.
Во-первых, в математике бесконечность обладает интереснным свойством - сколько к ней ни прибавляй (или отнимай) числа, она остается бесконечностью. Большие числа, которые мы используем в программе, этим свойством не обладают, поэтому его необходимо добавить искусственно. Просто будем считать все числа, больше либо равные половине "бесконечности", просто равными "бесконечности"
Во-вторых, если в графе много ребер отрицательного веса, то вес найденного алгоритмом Флойда цикла отрицательного веса будет очень быстро уменьшаться. Это может привести к нескольким последствиям:
- произойдет переполнение типа (при данных ограничения вес цикла может достигать -1040 (это легко проверить экспериментально))
- вес цикла станет по абсолютной величине больше "бесконечности"