Thảo luận:Định lý luồng cực đại lát cắt cực tiểu

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)

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.