1 Тема от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Тема: Алгоритм Диница или Шумахера???

Почитал на сайте статью про алгоритм Диница нахождения макс потока.
Закодил.

Решил поискатькуда можно его заакцептить.
нашел задачку с ограничением 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 секунды АС на самом большом тесте.

Это недостаток тестов, или быстродействие проверяющей машины???

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Алгоритм Диница или Шумахера???

Во-первых, O(N^2*M) это лишь порядок количества операций, т.е. там N^2*M*C, где C может быть <1.
Во-вторых, столько операций выполняется в худшем случае, в среднем же алгоритм работает быстро.
Вот ссылка на статью, где описан худший случай для алгоритма Диница: http://deepblue.lib.umich.edu/bitstream … 000617.pdf.

3 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Алгоритм Диница или Шумахера???

Вспоминается, в одном из петрозаводсков авторское решение искало Диницем поток среди 50000 вершин... smile

Сайтe-maxx

4 Ответ от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Re: Алгоритм Диница или Шумахера???

KADR пишет:

Во-первых, O(N^2*M) это лишь порядок количества операций, т.е. там N^2*M*C, где C может быть <1.
Во-вторых, столько операций выполняется в худшем случае, в среднем же алгоритм работает быстро.
Вот ссылка на статью, где описан худший случай для алгоритма Диница: http://deepblue.lib.umich.edu/bitstream … 000617.pdf.

Ну я прекрасно понимаю что такое асимптотика. И прикинуть приблизительно время программы можно.

Например такой цикл
    long long N,r,i;
    cin>>N;
    for(i=1;i<=N;i++) r=r+i;

отработал на моем ноутбуке, при N=10^9 - 10 секунд, при N = 2*10^9 - 21 секунду.

Если сравнить с временем АС = 0.3 то это раз в 70-100 медленнее.
Сомневаюсь что дело тут в константе C может быть <1 smile
Тут либо быстродействие проверяющей машины на несколько порядков выше smile
Либо не оптимальные тесты


e-maxx пишет:

Вспоминается, в одном из петрозаводсков авторское решение искало Диницем поток среди 50000 вершин... smile

Ну если там были единичные пропускные способности ребер, то O(sqrt(n)*m) может и вполне разумно, при неогромных m...

Кстати, а можно где то достать архивы петрозаводских сборов? (лекции, задачи, тесты, авторские решения)