Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 25.02.2009, 14:04
Новичок

Отправить личное сообщение для igor_ok-87 Посмотреть профиль Найти все сообщения от igor_ok-87
 
Регистрация: 25.02.2009
Сообщений: 2

форд-фалкерсон
если есть программа нахождения максимального потока методом Форда-Фалкерсона поделитесь, очень надо, заранее благодарю,
аська 318234859
мыло igor_ok-87@mail.ru
  #2  
Старый 25.02.2009, 14:46
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

В архиве 2007 есть
  #3  
Старый 19.03.2009, 16:37
Новичок

Отправить личное сообщение для =[miKroZ]= Посмотреть профиль Найти все сообщения от =[miKroZ]=
 
Регистрация: 07.01.2008
Адрес: Санкт-Петербург
Сообщений: 25

моя когдатошняя реализация:

Код:
// Матрица c - пропускные способности ребер
// f - собственно сюда будет считаться поток
// cf - вспомогательная матрица, в которой походу будет посчитана
// разность c - f
// cut - массив для запоминания посещенных вершин 
// (в конце концов после работы алгоритма из него будет
// получен минимальный разрез)
// p - массив предков. (p[u] - вершина, из которой мы попали в
// вершину u)


int c[maxn][maxn], f[maxn][maxn], cf[maxn][maxn];
int cut[maxn], p[maxn];
int n;

int bfs(int s, int t)
{
  memset(cut, 0, sizeof(cut));
  queue <int> q;
  
  q.push(s);
  
  while (!q.empty())
  {
    int u = q.front(); q.pop();
    for (int i = 0; i <= n; i++)
      if (cf[u][i] > 0 && !cut[i])
      {
        q.push(i);
        cut[i] = 1;
        p[i] = u;
      }
  }
  
  return cut[t];
}

int maxflow(int s, int t)
{
  memset(f, 0, sizeof(f));
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      cf[i][j] = c[i][j];
      
  while (bfs(s, t))
  {
    int u = t, cmin = inf;
    while (u != s)
    {
      if (cf[p[u]][u] < cmin)
        cmin = cf[p[u]][u];
      u = p[u];
    }
    u = t;
    while (u != s)
    {
      f[p[u]][u] += cmin;
      f[u][p[u]] -= cmin;
      cf[p[u]][u] = c[p[u]][u] - f[p[u]][u];
      cf[u][p[u]] = c[u][p[u]] - f[u][p[u]];
      u = p[u];
    }
  }
  int flow = 0;
  for (int i = 0; i <= n; i++)
    flow += f[i][t];
  return flow;
}
в итоге после чтения графа тебе достаточно запустить maxflow.
s и t (параметры maxflow) - исток и сток соответственно.
__________________
Irreparabilium felix oblivio rerrum.

Последний раз редактировалось =[miKroZ]=, 19.03.2009 в 16:39.
  #4  
Старый 23.04.2009, 19:45
гость

 
Сообщений: n/a

поясни пожалуйста что есть "n"
и что алгорим дает на выходе?
  #5  
Старый 23.04.2009, 20:38
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
поясни пожалуйста что есть "n"
Число вершин в графе минус 1. Вершины нгумеруется от 0 до n, включительно.

Цитата:
и что алгорим дает на выходе?
return value - величина макс. потока.
Содержимое массива f - (кососимметричные) величины потоков по каждому ребру.

Читай Кормена, там все подробно описано.
  #6  
Старый 24.04.2009, 01:20
гость

 
Сообщений: n/a

Спасибо за Кормена, действительно подробно...
еще такая просьба. плохо пока умею читать чужой код да и в теории не силен. а курсовик сдавать надо ....
как мне из этого кода получить НОМЕРА вершин графа принадлежащие к истоковому множеству (и стоковому соответственно...)
буду жутко благодарен за код (еще если с пояснениями)...
  #7  
Старый 24.04.2009, 01:47
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
как мне из этого кода получить НОМЕРА вершин графа принадлежащие к истоковому множеству
Это все вершина x, такие что cut[x]=1.
  #8  
Старый 12.05.2009, 16:09
Новичок

Отправить личное сообщение для Илья Посмотреть профиль Найти все сообщения от Илья
 
Регистрация: 12.05.2009
Сообщений: 3

Может кто полегче на пальцах объяснить как работает алгоритм Голдберга-Рао? У меня бакалаврат и вот тут такая проблема.
  #9  
Старый 26.03.2010, 11:17
гость

 
Сообщений: n/a

А это реализация на языке pascal???
  #10  
Старый 29.03.2010, 14:58
гость

 
Сообщений: n/a

на с
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра