PO
Я уже не проведу эксперименты и не воспроизведу)
Ну примерно?
Size: a a a
2020 December 09
@N
Ну примерно?
Не помню, считал total time, остальное не сильно интересовало
@N
достаточно было и тех результатов, что получились, чтоб выкинуть boost cycle cancelling
PO
Причем тебе надо прогнать 2 раза:
1) максимизация потока
2) с известным потоком с некотороей дельтой минимизируем сумму
1) максимизация потока
2) с известным потоком с некотороей дельтой минимизируем сумму
@N
Причем тебе надо прогнать 2 раза:
1) максимизация потока
2) с известным потоком с некотороей дельтой минимизируем сумму
1) максимизация потока
2) с известным потоком с некотороей дельтой минимизируем сумму
есть способ без "некоторой дельты" и без вспомогательного max flow как отдельного алгоритма это сделать
@N
но дважды прогнав алгоритм
@N
но да, проще один раз доп. max flow, ибо проще
PO
есть способ без "некоторой дельты" и без вспомогательного max flow как отдельного алгоритма это сделать
У тебя max flow не отдельный алгоритм
PO
Та же самая херня
PO
Просто разная цель минимизации + разница на одно ограничение
@N
У тебя max flow не отдельный алгоритм
ну а кто начальные баллансы на рёбрах расставлять будет?)
@N
можно и без max flow, поставив от балды, а потом посчитав дизбалланс в конце
PO
ну а кто начальные баллансы на рёбрах расставлять будет?)
Да фиг знает, я не писал симплекс метод ни разу в жизни)
@N
можно и без max flow, поставив от балды, а потом посчитав дизбалланс в конце
потом уже снова прогнать mcmf
@N
У тебя max flow не отдельный алгоритм
ну вообще нет)
@N
network simplex решает min cost flow, а уже max flow его делает расстановка баллансов, что в начале задаёшь)
@N
ему не нужен max flow внутри)
PO
network simplex решает min cost flow, а уже max flow его делает расстановка баллансов, что в начале задаёшь)
Ну я только краем уха слышал про network simplex
PO
А сам осиливаю придумать только через двойной прогон симплекс метода с макс флоу на первом шаге и по результатом достройки доп условия для мин кост
PO
Кстати, а что за задача то, что потребовала дробный мин кост?