Поиск максимальных потоков в сетях
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ПРИЛОЖЕНИЕ
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, DBGrids, AxCtrls, OleCtrls, VCF1, ComCtrls, StdCtrls;
type
TForm1 = class(TForm)
E11: TEdit; E21: TEdit; E31: TEdit; E41: TEdit; E51: TEdit; E61: TEdit;
E71: TEdit; E81: TEdit; E91: TEdit; E101: TEdit; E12: TEdit; E22: TEdit;
E32: TEdit; E42: TEdit; E52: TEdit; E62: TEdit; E72: TEdit; E82: TEdit;
E92: TEdit; E102: TEdit; E13: TEdit; E23: TEdit; E33: TEdit; E43: TEdit;
E53: TEdit; E63: TEdit; E73: TEdit; E83: TEdit; E93: TEdit; E103: TEdit;
E14: TEdit; E24: TEdit; E34: TEdit; E44: TEdit; E54: TEdit; E64: TEdit;
E74: TEdit; E84: TEdit; E94: TEdit; E104: TEdit; E15: TEdit; E25: TEdit;
E35: TEdit; E45: TEdit; E55: TEdit; E65: TEdit; E75: TEdit; E85: TEdit;
E95: TEdit; E105: TEdit; E16: TEdit; E26: TEdit; E36: TEdit; E46: TEdit;
E56: TEdit; E66: TEdit; E76: TEdit; E86: TEdit; E96: TEdit; E106: TEdit;
E17: TEdit; E27: TEdit; E37: TEdit; E47: TEdit; E57: TEdit; E67: TEdit;
E77: TEdit; E87: TEdit; E97: TEdit; E107: TEdit; E18: TEdit; E28: TEdit;
E38: TEdit; E48: TEdit; E58: TEdit; E68: TEdit; E78: TEdit; E88: TEdit;
E98: TEdit; E108: TEdit; E19: TEdit; E29: TEdit; E39: TEdit; E49: TEdit;
E59: TEdit; E69: TEdit; E79: TEdit; E89: TEdit; E99: TEdit; E109: TEdit;
E110: TEdit; E210: TEdit; E310: TEdit; E410: TEdit; E510: TEdit;
E610: TEdit; E710: TEdit; E810: TEdit; E910: TEdit; E1010: TEdit;
In11: TEdit; In21: TEdit; In31: TEdit; In41: TEdit; In51: TEdit;
In61: TEdit; In71: TEdit; In81: TEdit; In91: TEdit; In101: TEdit;
In12: TEdit; In22: TEdit; In32: TEdit; In42: TEdit; In52: TEdit;
In62: TEdit; In72: TEdit; In82: TEdit; In92: TEdit; In102: TEdit;
In13: TEdit; In23: TEdit; In33: TEdit; In43: TEdit; In53: TEdit;
In63: TEdit; In73: TEdit; In83: TEdit; In93: TEdit; In103: TEdit;
In14: TEdit; In24: TEdit; In34: TEdit; In44: TEdit; In54: TEdit;
In64: TEdit; In74: TEdit; In84: TEdit; In94: TEdit; In104: TEdit;
In15: TEdit; In25: TEdit; In35: TEdit; In45: TEdit; In55: TEdit;
In65: TEdit; In75: TEdit; In85: TEdit; In95: TEdit; In105: TEdit;
In16: TEdit; In26: TEdit; In36: TEdit; In46: TEdit; In56: TEdit;
In66: TEdit; In76: TEdit; In86: TEdit; In96: TEdit; In106: TEdit;
In17: TEdit; In27: TEdit; In37: TEdit; In47: TEdit; In57: TEdit;
In67: TEdit; In77: TEdit; In87: TEdit; In97: TEdit; In107: TEdit;
In18: TEdit; In28: TEdit; In38: TEdit; In48: TEdit; In58: TEdit;
In68: TEdit; In78: TEdit; In88: TEdit; In98: TEdit; In108: TEdit;
In19: TEdit; In29: TEdit; In39: TEdit; In49: TEdit; In59: TEdit;
In69: TEdit; In79: TEdit; In89: TEdit; In99: TEdit; In109: TEdit;
In110: TEdit; In210: TEdit; In310: TEdit; In410: TEdit; In510: TEdit;
In610: TEdit; In710: TEdit; In810: TEdit; In910: TEdit; In1010: TEdit;
ST1: TStaticText; ST2: TStaticText; ST3: TStaticText; ST4: TStaticText;
ST5: TStaticText; ST6: TStaticText; ST7: TStaticText; ST8: TStaticText;
ST9: TStaticText; ST10: TStaticText; OST1: TStaticText;
OST4: TStaticText; OST3: TStaticText; OST2: TStaticText;
OST5: TStaticText; OST6: TStaticText; OST7: TStaticText;
OST8: TStaticText; OST9: TStaticText; OST10: TStaticText;
VST1: TStaticText; VST2: TStaticText; VST3: TStaticText;
VST4: TStaticText; VST5: TStaticText; VST6: TStaticText;
VST7: TStaticText; VST8: TStaticText; VST9: TStaticText;
VST10: TStaticText; OVST1: TStaticText; OVST2: TStaticText;
OVST3: TStaticText; OVST4: TStaticText; OVST5: TStaticText;
OVST6: TStaticText; OVST7: TStaticText; OVST8: TStaticText;
OVST9: TStaticText; OVST10: TStaticText; SSS: TEdit;
StaticText41: TStaticText; TTT: TEdit; StaticText42: TStaticText;
Button1: TButton; StaticText43: TStaticText; StaticText44: TStaticText;
col: TEdit; label1: TLabel; Button2: TButton; Label2: TLabel;
max: TEdit; Button3: TButton; GB1: TGroupBox; Label3: TLabel;
Label4: TLabel; Label5: TLabel; Label6: TLabel; p1: TEdit;
p2: TEdit; p3: TEdit; p4: TEdit; Button4: TButton; Button5: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure FormClose(Sender: TObject; var Action: TCloseAction);
procedure FormCreate(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
function min(x,y: double): double;
const p1=10;
type
sign=(minus,plus);
ibool=0..1;
Rec=record
s:sign; {направление дуги}
n:1..p1; {предшествующая вершина в аугментальной цепи}
delta:double; {величина возможного увеличения потока}
end;
var
Form1: TForm1;
F: array of array of double;
P: array of Rec;
implementation
{$R *.dfm}
function min(x,y: double): double;
begin
if x < y then
Result := x
else
Result := y;
end;
procedure TForm1.Button1Click(Sender: TObject);
label M;
const p1=10;
type
sign=(minus,plus);
ibool=0..1;
Rec=record
s:sign; {направление дуги}
n:1..p1; {предшествующая вершина в аугментальной цепи}
delta:double; {величина возможного увеличения потока}
end;
var i,j: integer;
del,ch:double;
C,F: array of array of double;
P: array of Rec;
N,S: array of ibool;
a:ibool;
pp,s1,t1,x: byte;
input,output:array of array of TEdit;
begin
pp:=StrToInt(col.Text);
SetLength(input,pp);
SetLength(output,pp);
SetLength(C,pp);
SetLength(F,pp);
SetLength(P,pp);
SetLength(N,pp);
SetLength(S,pp);
for i:=0 to pp-1 do
begin
SetLength(input[i],pp);
SetLength(output[i],pp);
SetLength(C[i],pp);
SetLength(F[i],pp);
end;
for i:=1 to pp do
for j:=1 to pp do
begin
F[i-1,j-1] := 0; {вначале поток нулевой}
input[i-1,j-1]:=FindComponent(Format(In%d%d,[i,j])) as TEdit;
output[i-1,j-1]:=FindComponent(Format(E%d%d,[i,j])) as TEdit;
if input[i-1,j-1].Text<> then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)
else C[i-1,j-1]:=0;
end;
s1 := StrToInt(SSS.Text[2]);
if (s1=1) and (length(SSS.Text)=3) then
s1:=10;
t1 := StrToInt(TTT.Text[2]);
if (t1=1) and (length(TTT.Text)=3) then
t1:=10;
M: {итерация увеличения потока}
for i:=1 to pp do
begin
S[i-1] := 0;
N[i-1] := 0;
with P[i-1] do
begin
//s := null;
//n := nil;
delta := 0;
end;
end;
S[s1-1]:=1;
with P[s1-1] do
begin
s:=plus;
n:=s1;
end;
repeat
a:=0; {признак расширения S}
for i:=1 to pp do
begin
if (S[i-1]=1) and (N[i-1]=0) then
begin
for j:=1 to pp do
begin
if C[i-1,j-1]<>0 then
begin
if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := plus;
n := i;
if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]
else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);
end;
a := 1;
end;
end;
if C[j-1,i-1]<>0 then
begin
if (S[j-1]=0) and (F[j-1,i-1]>0) then
begin
S[j-1] := 1;
with P[j-1] do
begin
s := minus;
n := i;
if i=s1 then delta := F[j-1,i-1]
else delta := min(P[i-1].delta,F[j-1,i-1]);
end;
a:=1;
end;
end;
end;
N[i-1] := 1;
end;
end;
if S[t1-1]<>0 then
begin
x:=t1;
del:=P[t1-1].delta;
while x<>s1 do
begin
if P[x-1].s=plus then
F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del
else
F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;
x:=P[x-1].n
end;
goto M;
end;
until a=0;
ch:=0;
for i:=1 to pp do
begin
<