VPF::Алгоритм на графах. - Форум программистов

lansel

Дата 13.1.2006, 11:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 31
Регистрация: 3.1.2006

Репутация: нет
Всего: нет

Буду рада любой информации о алгоритме push-down. Зарание спасибо. smile

borisvolfson

Дата 15.1.2006, 19:23 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 44
Регистрация: 3.2.2005

Репутация: 2
Всего: 3

Новая игра - угадай алгоритм smile

Я так понимаю, что речь идет об алгоритме нахождения максимального потока в сети. Он хорошо описан в книге "Алгоритмы: построение и анализ" Кормен и компания. Вроде у меня где-то исходник даже валялся... если надо.

SoWa

Дата 15.1.2006, 21:18 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

А есть еще книжка Асанов М.А. "Дискретная оптимизация" Поищи там. Там все о графах

--------------------

Всем добра smile

Guest

Дата 15.1.2006, 23:02 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Это по какой то хоть теме. У меня вообще куча литературы по графам. Но я там ничего похежо на первом просмотре не нашел...
smile

lansel

Дата 16.1.2006, 11:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 31
Регистрация: 3.1.2006

Репутация: нет
Всего: нет

Цитата(borisvolfson @ 15.1.2006, 19:23)

Да ты прав речь идет об максимальном потоке.
Спасибо за книги, найду посмотрю....
От исходника тоже не откажусь smile

borisvolfson

Дата 16.1.2006, 19:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 44
Регистрация: 3.2.2005

Репутация: 2
Всего: 3

Не знаю насколько это тебе поможет... по-моему, не совсем та реализация, посмотри короче.

Код


{ cs.mipt.ru }
/*********************************************************
   Simple implementation of the push-relabel algorithm
   for the maximal network flow.
   Input format:
   n s t - number of nodes, source and sink
   then follow c[i][j], if i == j then number is ommited.
   See read() function.
*********************************************************/

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#include <list>

using namespace std;
const int N = 2000;

int e[N],c[N][N],h[N];
int n,s,t;


void push(int u,int v)
{
  int f = min(e[u],c[u][v]);
  e[u] -= f; e[v] += f;
  c[u][v] -= f; c[v][u] += f;
}

void lift(int u)
{
  int min = 3 * n + 1;
  
  for (int i = 0;i < n;i++)
    if (c[u][i] && (h[i] < min))
      min = h[i];
  h[u] = min + 1;
}

void discharge(int u)
{
  int v = 0;
  while (e[u] > 0)
  {
    if (c[u][v] && h[u] == h[v] + 1)
    {
      push(u,v); v = 0; continue;
    }
    v++;
    if (v == n)
    {
      lift(u); v = 0;
    }
  }
}

void read()
{
  cin >> n >> s >> t;
  
  for (int i = 0;i < n;i++)
    for (int j = 0;j < n;j++)
    {
      if (i == j)
        continue;
      cin >> c[i][j];
    }
}

void init()
{
  read();
  for (int i = 0;i < n;i++)
  {
    if (i == s)
      continue;
    e[i] = c[s][i]; c[i][s] += c[s][i];
  }
  h[s] = n;
}


int main(int argc, char *argv[])
{
  list<int> l;
  list<int>::iterator cur;
  int old;
  
  init();
  
  for (int i = 0;i < n;i++)
    if (i != s && i != t)
      l.push_front(i);
  cur = l.begin();
  
  while (cur != l.end())
  {
    old = h[*cur];
    discharge(*cur);
    if (h[*cur] != old)
    {
      l.push_front(*cur);l.erase(cur);cur = l.begin();
    }
    cur++;
  }
  cout << e[t];
  return 0;
}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »