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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 01.06.2010, 20:52
гость

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

максимальный поток в графе
Привет всем!!! Разбираюсь с алгоритмами максимального потока. Времени осталось очень мало. Скажите, пожалуйста, если исток s, сток t, а алгоритм дает в результате максимальный поток, то как найти матрицу максимального потока из s в t?
  #2  
Старый 01.06.2010, 21:22
гость

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

А шо это такое? И чем по вашему отличается от самого понятия максимальный поток?
  #3  
Старый 01.06.2010, 23:04
гость

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

во всех исходниках которые я нашел максимальный поток измеряется одним числом, а мне надо чтобы выводилась матрица максимальных пропускных способностей или матрица потоков по дугам
  #4  
Старый 02.06.2010, 02:43
гость

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

Сообщение от гость Посмотреть сообщение
во всех исходниках которые я нашел максимальный поток измеряется одним числом
это число называется величиной максимального потока

Цитата:
, а мне надо чтобы выводилась матрица максимальных пропускных способностей или матрица потоков по дугам
а содержимое этой матрицы - это и есть максимальный поток.

в алгоритме форда фалкерсона это матрица (или пропускные способности минус эта матрица) должна явно поддерживаться во время работы алгоритмы. если вы это еще не заметили, сходите к окулисту!

исходник в студию и я покажу где она там.
  #5  
Старый 02.06.2010, 02:47
гость

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

Сообщение от гость Посмотреть сообщение
а содержимое этой матрицы - это и есть максимальный поток.
ну а если точнее, то поток - это функция отображающая ребра графа в неотрицательные действительные числа, удовлетворяющие пропускным ограничением. а матрица - это просто один из способов представления этой функции (для графов без кратных ребер).
  #6  
Старый 02.06.2010, 03:04
гость

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

Исходник здесь. http://plagiata.net.ru/?p=465
Покажите где взять матрицу
  #7  
Старый 02.06.2010, 06:07
гость

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

то херня а не программа. где определение функции findway и глобальных переменных?
  #8  
Старый 02.06.2010, 06:09
гость

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

приводите полный исходник.

***И НИКАКИХ ССЫЛОК НА Е**НЫЕ ФАЙЛООБМЕННИКИ*** (я ценю своё время)
  #9  
Старый 02.06.2010, 11:35
гость

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

unit Unit8;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids;

type
TForm8 = class(TForm)
Label1: TLabel;
Edit1: TEdit;
Label2: TLabel;
Edit2: TEdit;
Button1: TButton;
StringGrid1: TStringGrid;
Label3: TLabel;
Edit3: TEdit;
Label4: TLabel;
Edit4: TEdit;
Memo1: TMemo;
Label5: TLabel;
Button2: TButton;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Edit2Exit(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

const
MaxV=1000;
MaxE=30000;

free_ = 0;
bisy_ = 1;
Great=MaxLongint;

var
Form8: TForm8;

implementation

{$R *.dfm}

procedure TForm8.FormCreate(Sender: TObject);
var i: integer;
begin
//Заполнить названия колонок в таблице
StringGrid1.Cells[0, 0] := 'Ребро';
StringGrid1.Cells[1, 0] := 'x';
StringGrid1.Cells[2, 0] := 'y';
StringGrid1.Cells[3, 0] := 'z';
for I := 1 to Pred(StringGrid1.RowCount) do
StringGrid1.Cells[0, i] := IntToStr(i);
//Для примера заполнить таблицу
StringGrid1.Cells[1, 1] := '1';
StringGrid1.Cells[1, 2] := '1';
StringGrid1.Cells[1, 3] := '2';
StringGrid1.Cells[1, 4] := '2';
StringGrid1.Cells[1, 5] := '3';
StringGrid1.Cells[1, 6] := '4';
StringGrid1.Cells[1, 7] := '5';
StringGrid1.Cells[2, 1] := '2';
StringGrid1.Cells[2, 2] := '3';
StringGrid1.Cells[2, 3] := '4';
StringGrid1.Cells[2, 4] := '5';
StringGrid1.Cells[2, 5] := '4';
StringGrid1.Cells[2, 6] := '6';
StringGrid1.Cells[2, 7] := '6';
StringGrid1.Cells[3, 1] := '1';
StringGrid1.Cells[3, 2] := '1';
StringGrid1.Cells[3, 3] := '1';
StringGrid1.Cells[3, 4] := '1';
StringGrid1.Cells[3, 5] := '1';
StringGrid1.Cells[3, 6] := '1';
StringGrid1.Cells[3, 7] := '1';
end;

procedure TForm8.Button1Click(Sender: TObject);
var
i: integer;
n, m, last, s, t, x, y, z: longint;
v,l: array[1..MaxV] of longint;
adj, next, c, f: array[1..MaxE] of longint;
found: boolean;
MaxPOTOK: longint;
prev: array [1..MaxV] of longint;
Marked: array [1..MaxV] of byte;
que,poz: array [1..MaxE] of longint;
qb,qe: longint;

procedure Init(n,m: longint);
var
i: longint;
begin
for i:=1 to n do
begin
v[i] := free_;
l[i] := free_;
end;
for i:=1 to 2*m do
begin
adj[i] := free_;
c[i] := free_;
next[i] := free_;
f[i] := free_;
end;
last := 0;
end;

procedure AddEdge(x,y,z: longint);
begin
inc(last);
adj[last] := y;
c[last] := z;
if v[x] = free_ then
begin
v[x] := last;
end else
begin
next[l[x]] := last;
end;
l[x] := last;
end;

procedure ErrorMes;
begin
ShowMessage('Неверно введены входные данные!');
exit
end;

procedure Put(x: longint);
begin
inc(qe);
que[qe]:=x;
Marked[x]:=bisy_;
prev[x]:=que[qb];
end;

procedure InitQue(x: longint);
var
i: longint;
begin
for i:=1 to 2*m do
begin
Marked[i]:=free_;
poz[i]:=0;
end;
qb:=1;
qe:=1;
que[qe] := x;
Marked[x] := bisy_;
end;

procedure FindWay;
var
x,Min,cf: longint;
begin
InitQue(s);
while (qb<=qe)and(Marked[t]<>bisy_) do
begin
x:=v[que[qb]];
while adj[x]<>free_ do
begin
if (Marked[adj[x]]<>bisy_)and(c[x]-f[x]>0) then
begin
Put(adj[x]);
poz[adj[x]]:=x;
end;
x:=next[x];
end;
inc(qb);
end;
if Marked[t]=free_ Then
begin
Found:=False;
Exit;
end;
Min:=Great;
x:=t;
while prev[x]<>free_ do
begin
cf:=c[poz[x]]-f[poz[x]]{!};
if cf<Min Then Min:=cf;
x:=prev[x];
end;
x:=t;
while prev[x]<>free_ do
begin
f[poz[x]]:=f[poz[x]]+Min;
if c[poz[x]]<>free_ then
f[poz[x]+1]:=-f[poz[x]]
else f[poz[x]-1]:=-f[poz[x]];
x:=prev[x];
end;
end;

begin

//Ввод данных

//Количество вершин
n := StrToIntDef(Edit1.Text, 0);
m := StrToIntDef(Edit2.Text, 0);
if (n = 0) or (m = 0) then ErrorMes;
Init(n,m);

//Матрица смежности
for i := 1 to m do
begin
x := StrToIntDef(StringGrid1.Cells[1, i], 0);
y := StrToIntDef(StringGrid1.Cells[2, i], 0);
z := StrToIntDef(StringGrid1.Cells[3, i], 0);
if (x <= 0) or (y <= 0) or (z <= 0) then ErrorMes;
AddEdge(x,y,z);
AddEdge(y,x,0);
end;

//Сток и исток (начальная и конечная вершины)
s := StrToIntDef(Edit3.Text, 0);
t := StrToIntDef(Edit4.Text, 0);
if (s > n) or (s <= 0) or (t > n) or (t <= 0) then ErrorMes;

//Вычисление по алгоритму Форда-Фалкерсона
found:=true;
while found do FindWay;
MaxPOTOK := 0;
x := v[s];
while x <> free_ do
begin
if f[x] > 0 then
MaxPOTOK := MaxPotok + f[x];
x:=next[x];
end;
Memo1.Lines.Clear;
Memo1.Lines.Add('Максимальный поток в заданном графе равен: '+ IntToStr(MaxPotok))
end;

procedure TForm8.Button2Click(Sender: TObject);
begin
Close
end;

procedure TForm8.Edit2Exit(Sender: TObject);
var i: integer;
m: longint;
begin
m := StrToIntDef(Edit2.Text, 0);
if m = 0 then
begin
ShowMessage('Неверно введены входные данные!');
exit
end;
StringGrid1.RowCount := m + 1;
for I := 1 to Pred(StringGrid1.RowCount) do
StringGrid1.Cells[0, i] := IntToStr(i);
end;

end.
  #10  
Старый 02.06.2010, 11:38
гость

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

здесь все переменные:

procedure TForm8.Button1Click(Sender: TObject);
var
i: integer;
n, m, last, s, t, x, y, z: longint;
v,l: array[1..MaxV] of longint;
adj, next, c, f: array[1..MaxE] of longint;
found: boolean;
MaxPOTOK: longint;
prev: array [1..MaxV] of longint;
Marked: array [1..MaxV] of byte;
que,poz: array [1..MaxE] of longint;
qb,qe: longint;
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
максимальный поток в ориентированном графе Parabol Графы 6 24.05.2010 01:57
максимальный поток гость Графы 7 29.04.2009 11:22
Максимальный поток гость Графы 1 31.08.2008 06:45
максимальный поток в графе с использованием параллельных вычислений kernel1987 Графы 0 19.04.2008 21:22
Максимальный поток MrFandorin Графы 3 14.04.2008 13:53