Динамический (с индексом по времени) Максимальный расход - Ford-Fulkerson

Question

Как вы можете изменить алгоритм Форда-Фулкерсона, чтобы учесть ограничение времени? Например, если вам было предоставлено максимальное количество времени, и каждый край занимает 1 единицу времени, как вы могли бы найти максимальный поток?

Answer 1

Обычный способ кодирования T временных шагов в задачах графа, чтобы сделать T+1 копии вершин графа, а затем для каждой дуги от u до v, сделать T из них, из u в копии i в v в копии i+1 для i от 0 до T-1.