Тема: Алгоритм Диница или Шумахера???
Почитал на сайте статью про алгоритм Диница нахождения макс потока.
Закодил.
Решил поискатькуда можно его заакцептить.
нашел задачку с ограничением 10 на число вершин
http://informatics.mccme.ru/moodle/mod/ … p?id=262#1
Здал успешно.
Смотрю дальше, и офигеваю. Задача с ограничениями на 500 вершин и 10000 ребер
http://informatics.mccme.ru/moodle/mod/ … rid=2784#1
Прикидываю, что если алгоритм Диница работает за O(n^2*m) то это будет порядка 2,5 миллиарда операций.
Смотрю ограничения времени - 2 секунды. думаю попробую...
И результат 0.3 секунды АС на самом большом тесте.
Это недостаток тестов, или быстродействие проверяющей машины???