Thảo luận:Định lý luồng cực đại lát cắt cực tiểu
Bách khoa toàn thư mở Wikipedia
[sửa] Tên bài
Bài này nên có tên chính là "Thuật toán Ford-Fulkerson" thay vì "Định lý luồng cực đại lát cắt cực tiểu". Mekong Bluesman 13:32, 9 tháng 8 2006 (UTC)
- Đã tạo bài mới với tên "Thuật toán Ford-Fulkerson" và định hướng "Định lý luồng cực đại" đến bài viết mới này vì hai khái niệm là như nhau trong lý thuyết đồ thị. QT 14:12, 9 tháng 8 2006 (UTC)QT
- Không hẳn đâu, tôi cũng đã nhầm như vậy. Mời bạn xem en:Max-flow min-cut theorem. Tmct 14:31, 9 tháng 8 2006 (UTC)
[sửa] Lập trình bằng Pascal
Const Vc = 1e9; Var N,M : integer;
s,t : integer;
g : text;
c : array[1..maxn,1..maxn] of integer;
f : array[1..maxn,1..maxn] of integer;
trace : array[1..maxn] of integer;
Procedure Readf; Var i,u,v:integer; Begin
Assign(g,fi);
reset(g);
Readln(g,n,m,s,t);
For i:=1 to m do
readln(g,u,v,c[u,v]);
Close(g);
End; function findpath:boolean; var q:array[1..maxn] of integer;
fr,ls:integer;
u,v:integer;
ch:array[1..maxn] of boolean;
Begin
Fillchar(q,sizeof(q),0);
Fillchar(trace,sizeof(trace),0);
fr:=1;
ls:=1;
ch[s]:=false;
q[1]:=s;
trace[s]:=n+1;
While fr<=ls do
Begin
u:=q[fr];
inc(fr);
For v:=1 to n do if (trace[v]=0) and(c[u,v]>f[u,v]) then
begin
trace[v]:=u;
if v=t then
Begin
findpath:=true;
exit;
End;
inc(ls);
q[ls]:=v;
End;
End;
findpath:=false;
End; Procedure incflow; Var d,u,v:integer; Begin
d:=maxint;
v:=t;
repeat
u:=trace[v];
if c[u,v]-f[u,v] < d then d:=c[u,v]-f[u,v];
v:=u;
Until v=s;
v:=t;
repeat
u:=trace[v];
f[u,v]:=f[u,v]+d;
f[v,u]:=f[v,u]-d;
v:=u;
until v=s;
End; Procedure writef; Var u,v:integer;
tong:integer;
Begin
assign(g,fo);
rewrite(g);
tong:=0;
For u:=1 to n do
for v:=1 to n do
if f[u,v]>0 then
Begin
Writeln(g,u,' ',v,' ',f[u,v]);
if u=s then inc(tong,f[u,v]);
End;
Writeln(g,tong);
close(g);
End; procedure main; Begin
repeat
if not(findpath) then break;
incflow;
Until false;
End; Begin
fillchar(f,sizeof(f),0);
Readf;
main;
writef;
End.

