VPF::Помогите написать программу Форда фалкерсона

Clockgen

Дата 4.9.2009, 14:42 (ссылка)

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

Загрузка ...

Новичок

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

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

Привет всем,помогите кто-нибудь реализовать это на паскале,ну просто намертво не хочет у меня находить пути,и делать сравнения потока с пропускной способностью,скачал реализацию на Делфи ничего не помогло,прошу помогите.

volvo877

Дата 4.9.2009, 17:50 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Clockgen @ 4.9.2009, 14:42

)

ну просто намертво не хочет у меня находить пути,и делать сравнения потока с пропускной способностью

Значит, что-то все-таки сделано? Вот и покажи, что пытался сделать сам...

Clockgen

Дата 5.9.2009, 17:27 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код


program l1;
uses crt;

const
  maxn = 100;                            { ¬ Єб. Є®«-ў® ўҐаиЁ }
  oo   = maxint;                         { ЎҐбЄ®Ґз®бвм }
  queue_size = maxn + 2;                { а §¬Ґа ®зҐаҐ¤Ё }

var
  { Ї®в®Є }
  f: array [1..maxn, 1..maxn] of integer;  { f[i, j] = -f[j, i] }
  { Їа®ЇгбЄлҐ бЇ®б®Ў®бвЁ }
  c: array [1..maxn, 1..maxn] of integer;
  { Є®«ЁзҐбвў® ўҐиаЁ}
  n: integer;

{- Џ®ЁбЄ ў иЁаЁг -}

{ ЋзҐаҐ¤м }

type
  queue = record                        { ®зҐаҐ¤м }
    a: array [0..queue_size-1] of integer;
    head, tail: integer;
  end;

{ init_queue: ЁЁжЁ «Ё§Ёа®ў вм ®зҐаҐ¤м }
procedure init_queue(var q: queue);
begin
  with q do
  begin
    tail := 0;
    head := 0;
  end;
end;

{ is_queue_empty: Їгбв  «Ё ®зҐаҐ¤м }
function is_queue_empty(const q: queue): boolean;
begin
  is_queue_empty := q.tail = q.head;
end;

{ push_to_queue: Ї®«®¦Ёвм ў ®зҐаҐ¤м x}
procedure push_to_queue(var q: queue; x: integer);
begin
  with q do
  begin
    a[tail] := x;
    tail := (tail + 1) mod queue_size;
  end;
end;

{ pop_from_queue: ¤®бв вм Ё§ ®зҐаҐ¤Ё }
function pop_from_queue(var q: queue): integer;
begin
  with q do
  begin
    pop_from_queue := a[head];
    head := (head + 1) mod queue_size;
  end;
end;

{ ЏҐаҐ¬ҐлҐ }

var
  { ®¬Ґа ЇаҐ¤л¤гйҐ© ўҐаиЁл}
  p: array [1..maxn] of integer;
  { Ї®бҐйҐ®бвм }
  v: array [1..maxn] of boolean;
  { ®зҐаҐ¤м }
  q: queue;

{ bfs: Ї®ЁбЄ ў иЁаЁг ¤«п ¬Ґв®¤  ”®а¤ -” «ЄҐаб®  }
{ ў®§ўа й Ґв true, Ґб«Ё бгйҐбвўгҐв Їгвм ®в s ¤® t }
function bfs(s, t: integer): boolean;
var
  i, j: integer;
begin
  fillchar(v, sizeof(v), false);        { ®Ўг«пҐ¬ ¬ ббЁў Ї®бҐйҐЁ© }
  init_queue(q);                        { ЁЁжЁ «Ё§ЁагҐ¬ ®зҐаҐ¤м }
  push_to_queue(q, s);                  { § в «ЄЁў Ґ¬ ў ®зҐаҐ¤м Ёбв®Є }
  v[s] := true;                         { Ї®бҐвЁ«Ё Ёбв®Є }
  p[s] := -1;                           { г Ёбв®Є  Ґв ЇаҐ¤Є  }

  while not is_queue_empty(q) do        { Ї®Є  ®зҐаҐ¤м Ґ Їгбв  }
  begin
    i := pop_from_queue(q);             { ¤®бв Ґ¬ ўҐаиЁг Ё§ ®зҐаҐ¤Ё }
    for j := 1 to n do                  { ЇҐаҐЎЁа Ґ¬ ўбҐ ўҐаиЁл }
      if not v[j] and                   { ўҐаиЁ  Ґ Ї®бҐйҐ  }
        (c[i, j]-f[i, j] > 0) then      { аҐЎа® i->j Ґ блйҐ®Ґ }
      begin
        v[j] := true;                   { Ї®бҐвЁ«Ё ўҐаиЁг j }
        push_to_queue(q, j);            { Ї®«®¦Ё«Ё ўҐаЁиЁг j ў ®зҐаҐ¤м }
        p[j] := i;                      { i ЇаҐ¤®Є j }
      end;
  end;
  bfs := v[t];                          { ¤®и«Ё «Ё ¤® бв®Є  }
end;

{- Ћб®ўлҐ Їа®жҐ¤гал -}

{ min: ¬ЁЁ¬г¬ Ё§ ¤ўге ўҐйҐбвўҐле зЁбҐ« }
function min(a, b: integer): integer;
begin
  if a > b then min := b else min := a;
end;

{ maxflow: § зҐЁп ¬ ЄбЁ¬ «м®Ј® Ї®в®Є  }
{ Ї®в®Є еа Ёвбп ў ¬ ваЁжҐ f, s-Ёбв®Є, t-бв®Є }
function maxflow(s, t: integer): integer;
var
  k: integer;
  d, flow: integer;
begin
  fillchar(f, sizeof(f), 0);            { ®Ўг«пҐ¬ f }
  flow := 0;                            { Ї®в®Є Їгбв®© }

  while bfs(s, t) do                    { Џ®Є  бгйҐбвўгҐв Їгвм ®в Ёбв®Є  ў }
  begin                                 { ў бв®Є ў ®бв в®з®© бҐвЁ, ЁйҐ¬   }
    d := oo;                            { аҐЎа® ў нв®¬ ЇгвЁ б ¬ЁЁ¬ «м®©  }
    k := t;                             { ҐЁбЇ®«м§®ў ®© Їа®ЇгбЄ®©      }
    while k <> s do                     { бЇ®б®Ў®бвмо                     }
    begin
      d := min(d, c[p[k], k]-f[p[k], k]);
      k := p[k];                        { ЎҐаҐ¬ ўҐаиЁг-ЇаҐ¤®Є }
    end;

    k := t;                             { Ё¤Ґ¬ Ї®  ©¤Ґ®¬г ЇгвЁ ®в бв®Є   }
    while k <> s do                     { Є Ёбв®Єг                         }
    begin
      f[p[k], k] := f[p[k], k] + d;     { гўҐ«ЁзЁў Ґ¬ Ї® Їап¬л¬ аҐЎа ¬ }
      f[k, p[k]] := f[k, p[k]] - d;     { г¬Ґми Ґ¬ Ї® ®Ўа вл¬ аҐЎа ¬ }
      k := p[k];                        { ЎҐаҐ¬ ўҐаиЁг-ЇаҐ¤®Є }
    end;

    flow := flow + d;                   { гўҐ«ЁзЁў Ґ¬ Ї®в®Є }
  end;

  maxflow := flow;                      { ў®§ўа й Ґ¬ ¬ ЄбЁ¬ «мл© Ї®в®Є }
end;

{ init: ЁЁжЁ «Ё§ жЁп Ё ўў®¤ ¤ ле }
procedure init;
var
  m, i, x, y, z: integer;
begin
  fillchar(c, sizeof(c), 0);

  assign(input, 'flow.in1');
  reset(input);

  read(n, m);

  for i := 1 to m do
  begin
    read(x, y, z);
    c[x, y] := z;
  end;

  close(input);
end;

{solve: аҐиҐЁҐ }
procedure solve;
begin
  writeln(maxflow(1, n));
end;

{- ѓ« ў п Їа®Ја ¬¬  -}

begin
  init;
  solve;
  readkey;
end.

Clockgen

Дата 5.9.2009, 18:05 (ссылка)

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

Загрузка ...

Новичок

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

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

Я задаю параметры для вычисления в программе максимального потока в текстовом файле матрицу 4х4 где 1 вершина-источник,4-я- сток.
т.е. так:

0 10 10 0
0 0   1   10
0 0   0   10
0 0   0   0

Ответ должен получиться 20,а получается 10 или вообще 5.Помогите пожалуйста.

volvo877

Дата 5.9.2009, 20:05 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Clockgen @ 5.9.2009, 18:05

)

Ответ должен получиться 20,а получается 10 или вообще 5

Ты запусти программу с контролем границ - она вообще вылетит. Ты чего из файла читаешь? Программа хочет, чтоб сначала в файле хранилось число строк/столбцов (читается Read(n, m)), потом должно читаться M троек чисел, и заполняться матрица. Так? Этого не произойдет, даже если добавить первыми двумя числами 4 и 4. Потому что на первой же тройке из файла прочитается X = 0, Y = 10, Z = 10, и при попытке обратиться к элементу c[0, 10] программа просто вылетит, чтобы это понять, даже нет необходимости ее запускать. Так что запиши данные в файл в нужном формате, зайди в Options->Compiler и отметь все пункты в группе "Runtime Errors", и никогда больше не снимай эти отметки.

А вот потом - запускай программу на выполнение.

Clockgen

Дата 6.9.2009, 11:18 (ссылка)

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

Загрузка ...

Новичок

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

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

Я не снимал галочки ,у меня вся программа выполняется,но только я так все таки не пойму как правильно написать программу,что такое x,y,z?
Помогите плиз,если x,y,z-для взвешенного графа то мне это не нужно,мне нужно задать параметры для mXn матрицы,задать источник,сток,и чтобы все находило правильно.Вы мне можете помоч?просто срочно необходима программа.

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