Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 04.09.2009, 16:12   #1
Clockgen
Пользователь
 
Регистрация: 20.11.2008
Сообщений: 66
Стрелка Помогите реализовать метод Форда Фалкерсона

Привет всем,помогите кто-нибудь реализовать это на паскале,ну просто намертво не хочет у меня находить пути,и делать сравнения потока с пропускной способностью,скачал реализацию на Делфи и С++ ничего не помогло,прошу помогите.
Clockgen вне форума Ответить с цитированием
Старый 05.09.2009, 09:49   #2
ОДИНОЧЕСТВО В СЕТИ
Любопытная Вредина
Участник клуба
 
Аватар для ОДИНОЧЕСТВО В СЕТИ
 
Регистрация: 19.06.2009
Сообщений: 1,285
По умолчанию

Код:
//(C) автор:  Igor Kvasov
{поиск максимального потока методом Форда-Фалкерсона;
для поиска дополняющего пути используется поиск в ширину}
const
  maxn = 1000;
  infinity = maxlongint;
var
  n,m,vin,vout,i,u,v,w,head,tail,ans:longint;
  ne,p,flow:array[1..maxn]of longint;
  e,c,f:array[1..maxn,1..maxn]of longint;
  q:array[0..maxn]of longint;

begin
  read(n,m,vin,vout);
  for i:=1 to m do begin
    read(u,v,w);
    if c[v,u]=0 then begin
      inc(ne[u]); e[u,ne[u]]:=v;
      inc(ne[v]); e[v,ne[v]]:=u;
    end;
    c[u,v]:=w;
  end;
  repeat
    p[vout]:=-1;
    fillchar(flow,sizeof(flow),0);
    flow[vin]:=infinity;
    head:=0; tail:=1; Q[0]:=vin;
    while head<tail do begin
      u:=Q[head]; inc(head);
      for i:=1 to ne[u] do begin
        v:=e[u,i];
        if (c[u,v]-f[u,v]>0)and(flow[v]=0) then begin
          Q[tail]:=v; inc(tail);
          p[v]:=u;
          if c[u,v]-f[u,v]<flow[u] then flow[v]:=c[u,v]-f[u,v]
                                   else flow[v]:=flow[u];
          if v=vout then break;
        end;
      end;
    end;
    if p[vout]=-1 then break;
    u:=vout;
    while u<>vin do begin
      f[p[u],u]:=f[p[u],u]+flow[vout];
      u:=p[u];
    end;
    ans:=ans+flow[vout];
  until false;
  write(ans);
end.
Дурь - это особая форма материи, которая не возникает ниоткуда и не исчезает никуда, а лишь переходит из одной головы в другую.
ОДИНОЧЕСТВО В СЕТИ вне форума Ответить с цитированием
Старый 05.09.2009, 18:53   #3
Clockgen
Пользователь
 
Регистрация: 20.11.2008
Сообщений: 66
По умолчанию

Хороший код но считает он не правильно,или подскажи какими параметрами его нужно заполнять при выполнении?
Почему не правильно считает,потому что,когда у меня имеется 4 вершины получается матрица 4х4 где 1 вершина источник,а 4-я сток и получается у меня матрица:
1 2 3 4
1 0 10 10 0
2 0 0 1 10
3 0 0 0 10
4 0 0 0 0

По правилу в основной диагонали матрицы не может быть числа(Дискретная математика),и при вводе этой матрицы программа выдает мне в ответе 5,хотя ответ должен быть 20,что надо сделать?как надо исправить код,чтобы ответ был именно 20?
Clockgen вне форума Ответить с цитированием
Старый 23.04.2014, 22:45   #4
Mastdrak
 
Регистрация: 09.04.2014
Сообщений: 4
По умолчанию

Представь пожалуйста код на С++, уж больно хочется на него взглянуть
Mastdrak вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

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

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Безумно сложные задачки!!!! Метод Гаусса, итераций, метод половинного деления, задача Коши и т.д. Хомяк!!!!! Помощь студентам 4 08.07.2009 10:08
алгоритм Форда-Беллмана Foky Паскаль, Turbo Pascal, PascalABC.NET 1 19.10.2008 17:27
Помогите реализовать ReacXX Общие вопросы Delphi 3 26.05.2008 08:56
Помогите реализовать VenMaster Общие вопросы Delphi 8 24.04.2008 23:45