Для поиска максимального потока в графе с одним истоком




Скачать 76.57 Kb.
НазваниеДля поиска максимального потока в графе с одним истоком
Дата публикации27.03.2014
Размер76.57 Kb.
ТипДокументы
uchebilka.ru > Астрономия > Документы
ПОТОКИ В СЕТЯХ
Для поиска максимального потока в графе с одним истоком s и одним стоком t воспользуемся алгоритмом Эдмондса – Карпа. Положим изначально значение максимального потока Flow равным нулю. Ищем путь из s в t поиском в ширину. Если такого пути нет, то заканчиваем алгоритм, возвращая значение найденного максимального потока Flow. Иначе по найденному пути пропускаем максимально возможный поток. Для этого ищем в этом пути ребро с наименьшей пропускной способностью w. Пропускаем по пути поток величины w, добавляем w к Flow. Далее следует пересчитать пропускные способности ребер на пути из s в t.
Max_Flow(G, s, t)

Flow = 0;

while(существует путь из s в t, найденный поиском в ширину) do

begin

ищем в найденном пути ребро с наименьшей пропускной способностью w;

Flow = Flow + w;

проводим пересчет пропускных способностей ребер на пути из s в t;

end;

return Flow;
1. Максимальный поток. Найти величину максимального потока в графе между вершинами s и t.

Вход. Первая строка содержит количество вершин n в графе, а также номера вершин s и t. Каждая следующая строка содержит три целых числа u, v и w, описывая ребро (u, v) графа с пропускной способностью w.

Выход. Вывести величину максимального потока в графе между вершинами s и t в формате, представленном ниже.

Пример входа

Пример выхода

6 0 5

Maximal Flow is: 17

0 1 20




1 2 1




2 5 15




0 3 7




3 2 20




1 4 18




4 5 9




3 4 10





Граф, представленный в примере, имеет вид:



Величина максимального потока между вершинами 0 и 5 равна 17. Распределение потока по ребрам представлено ниже. Возле каждого ребра стоит метка “загрузка ребра / пропускная способность ребра”. Ребра, входящие в минимальный разрез, выделены жирным.



^ 2. Сурок 2 [Вальядолид, 10080]. Имеются n сурков и m нор, заданные уникальными координатами (x, y). Ястреб съест сурка, если тот не спрячется в нору в течение s секунд. Все сурки имеют одинаковую скорость передвижения v. В каждой норе может спрятаться не более одного сурка. Суркам следует разработать стратегию, согласно которой они рассредоточатся по норам. При этом число доступных ястребу сурков через s секунд должно быть минимально. Определить наименьшее число сурков, которое не сможет спрятаться от ястреба.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит четыре натуральных числа n, m, s, v. Следующие n строк описывают координаты сурков, за которыми идут m строк с координатами нор.

Выход. Для каждого теста вывести наименьшее число сурков, которое не сможет спрятаться от ястреба.

Пример входа

Пример выхода

2 2 5 10

1

1.0 1.0




2.0 2.0




100.0 100.0




20.0 20.0





^ 3. Эйлеров путь [Вальядолид, 10735]. Имеется граф, который имеет как ориентированные, так и неориентированные ребра. Можно ли ориентировать неориентированные ребра так, чтобы полученный граф имел эйлеров цикл?

Вход. Первая строка содержит количество входных тестов T (1  T  20). Каждый тест начинается со строки, содержащей число вершин V (1  V  100) и число ребер E (1  E  500). Вершины пронумерованы числами от 1 до V. Далее следует E строк, описывающих ребра графа.

Выход. Для каждого теста вывести в отдельной строке его номер и количество троек чисел (a, b, m), удовлетворяющих заданным условиям.

Пример входа

Пример выхода

2

1 3 4 2 5 6 5 4 1

6 8

 

1 3 U

No euler circuit exist

1 4 U




2 4 U




2 5 D




3 4 D




4 5 U




5 6 D




5 6 U




4 4




1 2 D




1 4 D




2 3 U




3 4 U




^ УКАЗАНИЯ И РЕШЕНИЯ
1. Максимальный поток. Максимально возможное число вершин в графе храним в MAX. Массив m содержит матрицу смежности, массивы used и parent будут использоваться при поиске в ширину.
#include

#include

#include

#include
using namespace std;

const int MAX = 20;

int m[MAX][MAX];

int used[MAX],parent[MAX];

int source,dest,n;

deque q;
Функция совершает поиск в ширину. Используется очередь q. Одновременно с обходом вершин графа в ширину строится массив parent, для которого parent[i] = j, если из вершины j попали в вершину i. Массив строится для возможности восстановить сам путь из s в t.
void bfs(int v)

{

int i,First;

q.push_front(v);

while(!q.empty())

{

First = q[0];

if (First == dest) return;

q.pop_front();

used[First] = 1;

for(i=0;i
if ((m[First][i] > 0) && (!used[i]))

{

parent[i] = First;

q.push_back(i);

}

}

}
Функция Rebuild совершает пересчет пропускных способностей ребер на пути из s в t. Пропускная способность пути содержится в переменной flow. Если на каком-то шаге parent[k] = -1, то вершина k является начальной. Для каждого ребра (parent[k], k) пути уменьшаем его пропускную способность в прямом направлении и увеличиваем в обратном.
void Rebuild(int k, int flow)

{

if (parent[k] == -1) return;

Rebuild(parent[k],flow);

m[parent[k]][k] -= flow;

m[k][parent[k]] += flow;

}
Функция min вычисляет минимум двух чисел i и j.
int min(int i, int j)

{

return (i < j) ? i : j;

}
Функция FindFlow производит поиск максимальной пропускной способности от s к t по пути, найденном поиском в ширину. Она равна наименьшей пропускной способности ребра, входящего в этот путь. Если пути от истока к стоку не существует, функция FindFlow возвращает INT_MAX.
int FindFlow(int k)

{

int x;

if (parent[k] == -1) return INT_MAX;

x = FindFlow(parent[k]);

return min(x,m[parent[k]][k]);

}
void main(void)

{

int a,b,c;

int MaxFlow,flow;
Обнуляем матрицу смежности графа. Читаем входные данные.
memset(m,0,sizeof(m));

scanf("%d %d %d\n",&n,&source,&dest);

while (scanf("%d %d %d\n",&a,&b,&c) == 3) m[a][b] = c;
Начальное значение максимального потока ^ MaxFlow установим равным нулю. Пока существует путь из s в t, ищем его пропускную способность flow, увеличиваем MaxFlow на это значение и совершаем пересчет пропускных способностей ребер на пути из source в dest.
MaxFlow = 0;

while (1)

{

q.clear();

memset(parent,-1,sizeof(parent)); memset(used,0,sizeof(used));

bfs(source);

flow = FindFlow(dest); if (flow == INT_MAX) break;

MaxFlow += flow;

Rebuild(dest,flow);

}
Выводим искомое значение максимального потока.
printf("Maximal Flow is: %d\n",MaxFlow);

}
^ 3. Эйлеров путь. Перенумеруем неориентированные ребра. Построим двудольный граф. Одному множеству вершин соответствуют вершины графа Vi, другому – неориентированные ребра ei. От каждой вершины ei проведем ребра к тем вершинам Vj, к которым они могут быть направлены. Пропускные способности этих ребер ставим равными 1.

Для существования Эйлерового цикла в ориентированном графе необходимо, чтобы для каждой вершины количество входящих ребер равнялось количеству выходящих. Возле каждой вершины исходного графа в скобках припишем метки mi, равные количеству неориентированных ребер, которые должны входить в эту вершину.

Например, рассмотрим вершину V2. Из нее выходит 4 ребра, одно из которых ориентированное. Для существования Эйлерового цикла в вершину V2 должно входить 2 ребра и два из нее выходить. То есть два неориентированных ребра необходимо ориентировать так, чтобы они входили в V2. Вершина V3 имеет метку 1, так как только одно из неориентированных ребер должно входить в V3.

В двудольном графе добавим две вершины – исток S и сток D. Каждое ребро может быть ориентировано только в одну сторону, поэтому пропускные способности ребер, соединяющих вершины S и ei, установим равными 1. В вершину Vi должно быть направлено mi ребер, поэтому пропускные способности ребер, соединяющих вершины Vi и D, установим равными mi.

Ищем максимальный поток в построенном графе между вершинами S и D. Если его величина равна количеству неориентированных ребер, то Эйлеров цикл существует.






СПИСОК ИСПОЛЬЗОВАННЫХ ЗАДАЧ
[Вальядолид] acm.uva.es/problemset:

10080 (Сурок 2) ,10735 (Эйлеров путь).

Добавить документ в свой блог или на сайт

Похожие:

Для поиска максимального потока в графе с одним истоком iconОписывается один из классических методов поиска в графе поиск в глубину....
Представлена реализация поиска в глубину на несвязном (ориентированном) графе. Описана техника раскраски вершин и расстановки меток....

Для поиска максимального потока в графе с одним истоком iconОписывается один из классических методов поиска в графе поиск в глубину....
Представлена реализация поиска в глубину на несвязном (ориентированном) графе. Описана техника раскраски вершин и расстановки меток....

Для поиска максимального потока в графе с одним истоком iconИ. В. Максимей, Е. И. Сукач, П. В. Гируц использование имитационного...
Предлагается использование обобщённой имитационной модели региональной транспортной сети, учитывающей влияние случайных внутренних...

Для поиска максимального потока в графе с одним истоком iconІнформаційно-аналітичні системи обробки даних
Предложено использование обобщенной имитационной модели региональной транспортной сети, учитывающей влияние случайных внутренних...

Для поиска максимального потока в графе с одним истоком iconО разложении конечного бернуллиевского источника многозначных последовательностей
К задачам сжатия относятся сейчас не только задачи уменьшения длины передаваемых или хранимых сообщений, а и задачи построения оптимальных...

Для поиска максимального потока в графе с одним истоком iconДвоичное дерево поиска
Задание. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями...

Для поиска максимального потока в графе с одним истоком iconЗадача остовных деревьев в k-связном графе Министерство Науки и Образования...

Для поиска максимального потока в графе с одним истоком iconСоздание системы поиска информации в корпоративной сети
Рассмотрены особенности поиска информации для обеспечения аналитической деятельности пользователей корпоративных сетей, предложена...

Для поиска максимального потока в графе с одним истоком iconД. А. Рачковский, И. С. Мисуно, С. В. Слипченко, А. М. Соколов
Показано, что степень сходства ситуаций можно оценить по величине скалярного произведения представляющих их векторов. Это создает...

Для поиска максимального потока в графе с одним истоком iconПрограммно-аппаратный комплекс учета и анализа потока посетителей “Privat Count”
Программа “Privat Count” предназначена для постоянного измерения потока посетителей в магазинах, супермаркетах, торговых комплексах...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<