Редактирование: Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 44: Строка 44:
 
===Реализация===
 
===Реализация===
  
Пусть задана структура <tex>Edge</tex>:
+
  '''double[][]''' findMinCostMaxFlow('''pair<int, int>''' E, '''double[][]''' C, '''double[][]''' P, '''int''' s, '''int''' t):  
  '''struct''' edge:
+
     '''for''' (u, v) '''in''' <tex>E</tex>:
    '''int''' from       
+
         flow[u][v] = 0
    '''int''' to             
 
    '''double''' c      <font color=green>// пропускная способность ребра</font>
 
    '''double''' flow    <font color=green>// поток через ребро</font>
 
    '''double''' price  <font color=green>// стоимость перемещения единицы потока через ребро</font>
 
 
 
Будем использовать структуру для хранения ребер графа G.
 
 
 
'''Edge[]''' findMinCostMaxFlow(<tex>G: (V, E)</tex>, '''int''' s, '''int''' t):  
 
     '''for''' edge '''in''' <tex>E</tex>:
 
         edge.flow = 0
 
 
     '''while''' <tex>\exists</tex> путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>:
 
     '''while''' <tex>\exists</tex> путь <tex>s \leadsto t</tex> в остаточной сети <tex>G_f</tex>:
         P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью.
+
         path = путь <tex>s \leadsto t</tex> с наименьшей стоимостью P
         maxFlow = <tex>\displaystyle  \min_{edge \in P} edge.c - edge.flow</tex>
+
         maxFlow = <tex>\displaystyle  \min_{(u, v) \in path} C[u][v] - flow[u][v]</tex>
         '''for''' edge '''in''' P:
+
         '''for''' (u, v) '''in''' path:
             edge.flow += maxFlow
+
             flow[u][v] = flow[u][v] + maxFlow
     '''return''' <tex>E</tex>
+
     '''return''' flow
  
 
===Асимптотика===
 
===Асимптотика===

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: