Алгоритм Форда-Фалкерсона

@Олег1000 · Регистрация: 21.04.2019

Author24 — интернет-сервис помощи студентам

Нужен код алгоритма Форда-Фалкерсона. Нигде не нашел рабочий вариант. А те, что нашел, не работают и содержат кучу мусора.

@Kuzia domovenok · 22.11.2019, 10:55

код покажи, что не получается.

Добавлено через 20 минут

@Олег1000 · 23.11.2019, 05:59 **[ТС]**

Видео смотрел. Знаю, как реализовать метод графически и в виде математического выражения, но как код писать без понятия. Про те, что не работают, я говорю про обрывки кодов на stackoverfow и здесь, где спрашивают вопросы вроде "я тут набросал че-то это правильно? Что дальше делать?".

@gunslinger · 23.11.2019, 06:42

Большой проблемы перевести на С++ возникнуть не должно.
Реализация поиска максимального потока методом Форда-Фалкерсона на Java - Maximum flow. Ford-Fulkerson alogithm in O(V^2 * FLOW):
https://sites.google.com/site/... _fulkerson

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 public class MaxFlowFordFulkerson {
 
  public static int maxFlow(int[][] cap, int s, int t) {
    for (int flow = 0;;) {
      int df = findPath(cap, new boolean[cap.length], s, t, Integer.MAX_VALUE);
      if (df == 0)
        return flow;
      flow += df;
    }
  }
 
  static int findPath(int[][] cap, boolean[] vis, int u, int t, int f) {
    if (u == t)
      return f;
    vis[u] = true;
    for (int v = 0; v < vis.length; v++)
      if (!vis[v] && cap[u][v] > 0) {
        int df = findPath(cap, vis, v, t, Math.min(f, cap[u][v]));
        if (df > 0) {
          cap[u][v] -= df;
          cap[v][u] += df;
          return df;
        }
      }
    return 0;
  }
 
  // Usage example
  public static void main(String[] args) {
    int[][] capacity = { { 0, 3, 2 }, { 0, 0, 2 }, { 0, 0, 0 } };
    System.out.println(4 == maxFlow(capacity, 0, 2));
  }
}

@Kuzia domovenok · 23.11.2019, 10:16

Олег1000, настоящему программисту должно быть достаточно видео,
это студенты смотрят в книгу и разбор сортировки пузырьком понять не могут

@Олег1000 · 23.11.2019, 11:49 **[ТС]**

Сообщение от Kuzia domovenok

Олег1000, настоящему программисту должно быть достаточно видео,
это студенты смотрят в книгу и разбор сортировки пузырьком понять не могут

Вы абсолютно правы :-)

Новые блоги и статьи Все статьи Все блоги /
sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .	SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .
Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .	Lazarus. Таблица с объединением ячеек. Massaraksh7 21.03.2025 Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .	Async/await в Swift: Асинхронное программирование в iOS mobDevWorks 20.03.2025 Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .

@Олег1000 24 / 19 / 8 Регистрация: 21.04.2019 Сообщений: 494

	Алгоритм Форда-Фалкерсона 22.11.2019, 07:25. Показов 18942. Ответов 5 Метки c++ (Все метки) Нужен код алгоритма Форда-Фалкерсона. Нигде не нашел рабочий вариант. А те, что нашел, не работают и содержат кучу мусора. 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,521 Записей в блоге: 1
	22.11.2019, 10:55
	код покажи, что не получается. Добавлено через 20 минут 0

@Олег1000 24 / 19 / 8 Регистрация: 21.04.2019 Сообщений: 494
	23.11.2019, 05:59 [ТС]
	Видео смотрел. Знаю, как реализовать метод графически и в виде математического выражения, но как код писать без понятия. Про те, что не работают, я говорю про обрывки кодов на stackoverfow и здесь, где спрашивают вопросы вроде "я тут набросал че-то это правильно? Что дальше делать?". 0

@Kuzia domovenok 4264 / 3323 / 925 Регистрация: 25.03.2012 Сообщений: 12,521 Записей в блоге: 1
	23.11.2019, 10:16
	Олег1000, настоящему программисту должно быть достаточно видео, это студенты смотрят в книгу и разбор сортировки пузырьком понять не могут 0

@Олег1000 24 / 19 / 8 Регистрация: 21.04.2019 Сообщений: 494
	23.11.2019, 11:49 [ТС]
	Сообщение от Kuzia domovenok Олег1000, настоящему программисту должно быть достаточно видео, это студенты смотрят в книгу и разбор сортировки пузырьком понять не могут Вы абсолютно правы :-) 1

Опции темы