Вопросы по теме 'max-flow'
Максимальный поток в динамических графиках
Я ищу быстрый алгоритм для вычисления максимального потока в динамических графах (добавление/удаление узла со связанными ребрами в графе). то есть у нас есть максимальный поток в G, теперь новый узел добавлен/удален со связанными ребрами, мне не...
1680 просмотров
schedule
24.01.2023
Алгоритм назначения библиотечных книг участникам таким образом, чтобы максимальное количество участников было удовлетворено
Мне дали задачу на классном тесте. В библиотеке каждый член запрашивал четыре книги, и каждую книгу запрашивали только два члена. Эта информация представлена в виде двудольного графа G = (X + Y, E)
X : множество всех элементов Y : множество...
123 просмотров
schedule
07.03.2024
Увеличьте поток, изменив только одну кромку по Форду-Фулкерсону.
Предположим, что я запустил алгоритм Форда-Фалкерсона на графе G = (V,E) и в результате получил максимальный поток f max , связанный с минимальным разрезом Xmin. Я заинтересован в максимально возможном увеличении потока за счет увеличения пропускной...
6708 просмотров
schedule
04.05.2023
Модификация алгоритма максимального потока
Я попытался решить вопрос о проблеме максимального потока . У меня один источник и два стока. Мне нужно найти максимальный поток в этой сети. Эта часть является общим максимальным потоком. Однако в этой специальной версии задачи о максимальном...
1041 просмотров
schedule
24.07.2022
максимальное двудольное паросочетание (Форд-Фулкерсон)
Я читал http://www.geeksforgeeks.org/maximum-bipartite-matching/ и http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm , и у меня возникли проблемы понимание. Кажется, пример основан на предположениях, что каждая работа может принимать...
4843 просмотров
schedule
14.05.2023
Как я могу получить элементы антицепи в SPOJ-DIVREL?
Проблема: http://www.spoj.com/problems/DIVREL
В вопросе нам просто нужно найти максимальное количество элементов, которые не являются кратными (форма a делится на b) из заданного набора элементов. Если мы просто сделаем ребро от элемента к его...
1107 просмотров
schedule
26.05.2023
Сегментация изображения с помощью maxflow
Мне нужно выполнить сегментацию переднего/фонового плана с использованием алгоритма maxflow на С++. ( http://wiki.icub.org/iCub/contrib/dox/html/poeticon_2src_2objSeg_2src_2maxflow-v3_802_2maxflow_8cpp_source.html ). Я получаю массив пикселей из...
3554 просмотров
schedule
09.01.2024
Дети профессора Адама (определить максимальный поток)
Мне нужна помощь в понимании того, как решить следующую проблему:
У профессора Адама двое детей, которые, к сожалению, недолюбливают друг друга. Проблема настолько серьезна, что они не только отказываются вместе ходить в школу, но фактически...
2042 просмотров
schedule
12.05.2024
Теория графов - глобально минимальное сечение и его последствия
Для взвешенного ориентированного графа мы хотим найти глобально минимальный разрез, то есть набор ребер, которые при удалении делят граф на две половины и которые имеют минимальный общий вес по сравнению с любым другим таким разрезом.
Теперь, хотя...
387 просмотров
schedule
15.06.2022
как использовать алгоритм Диника для поиска ребер с минимальным вырезом в ненаправленном графе?
Я ищу алгоритм, когда заданы два узла 's' и 't' в ненаправленном графе, чтобы найти ребра с минимальным разрезом, которые разбивают граф на два A и B, 's' будет в A и 't ' будет в Б.
Я вижу, что большинство людей предлагают алгоритм...
1339 просмотров
schedule
07.07.2022
Как узнать, находится ли ребро на каком-то пути
Дан неориентированный граф G=V,E, 2 вершины: x, y и ребро e,
Я хотел бы проверить, существует ли путь от x до y, который содержит данное ребро e.
Что я подумал: решите это, определив сетевой поток, где x и y являются источником и приемником, и...
65 просмотров
schedule
19.07.2022
Как показать, что объединение и пересечение минимальных разрезов в сети потоков также является минимальным разрезом
Доказательство этого везде пропускается и считается следствием теоремы Min-Cut-Max-Flow ... Обычно это что-то вроде:
Пусть S1 и S2 — минимальные разрезы поточной сети. Тогда S1∪S1 и S1∩S2 также являются минимальными разрезами.
Кто-нибудь может...
3592 просмотров
schedule
15.12.2022
Количество мин. резов при максимальном расходе
У меня есть этот вопрос, на котором я застрял.
Для сети N найдите количество минимальных разрезов. требуемая временная сложность: Poly(|N|) * #(мин. разрезов).
Мне не удалось найти ничего полезного, кроме как найти первый минимальный...
724 просмотров
schedule
26.01.2023
Как построить график уровней для алгоритма Диника для вычисления максимального потока?
Я читал об алгоритме Диника для решения проблемы максимального потока, и алгоритм утверждает следующее. для графа G с заданным источником S и стоком T:
Установите поток каждого ребра на 0
Построить граф уровня GL по Gf (где Gf — остаточный...
747 просмотров
schedule
31.07.2023
Изменение реализации Java Ford Fulkerson для печати максимального потока, используемого на каждом ребре в решении максимального потока?
Я хочу изменить эту реализацию алгоритма Форда-Фулкерсона. алгоритм (также размещен ниже), чтобы я мог графически отображать узлы и анализировать данные. Я хотел бы не только вывести максимальный поток, но и максимальный поток на каждом ребре,...
708 просмотров
schedule
03.05.2022
Спасательные капсулы Google Foobar Challenge | Проблема с максимальным расходом
Я нахожусь на 4-м уровне конкурса google foobar. И я сталкиваюсь с проблемами в вопросе. Я попробовал свое решение на предоставленных тестовых примерах, но средство проверки оценок Google показывает, что мой код неверен и для этих тестовых случаев....
546 просмотров
schedule
30.09.2022
