Вычислить максимальный поток для сетей

Question

можем ли мы найти алгоритм, который вычисляет (в линейном времени) максимальный поток для древовидных сетей, то есть для сетей, в которых удаление приемника (и связанных с ним ребер) оставляет дерево.

Answer 1

Да, просто запустите что-то вроде следующего:

maxf(s) {
  if (s == sink) return s.in_capacity;
  ret = 0;
  foreach(c in children(s)) ret += maxf(c);
  return min(ret, s.in_capacity);
}

Используйте начальный вызов с s равным источнику (мы предполагаем, что источник имеет бесконечность in_capacity).

Answer 2

Форд-Фулкерсон - это O (E * f), где E - это число ребер, а f - максимальный поток, который считается линейным, если в вашей задаче есть постоянная верхняя граница для E или f.