У меня проблема: дан график, который содержит ребра с весами в диапазоне 1 ... K. Я должен разработать алгоритм, который рассчитывает максимальный поток и занимает меньше времени, чем O (n ^ 3).
У нас есть дополнительная подсказка для использования потока блокировки с комбинацией некоторой структуры данных.
Моя идея:
использовать алгоритм Диника с динамическими деревьями -> O (VE logV), но это все еще слишком медленно (потому что для плотных графов E примерно n ^ 2).
Пожалуйста, помогите мне:)