Luồng cực đại, using Ford-Fulkerson Algorithm

Hướng dẫn: Doc tai lieu cua Le Minh Hoang – phien ban cuoi cung

Input:

6 8 1 6
1 2 5
1 3 5
2 4 6
2 5 3
3 4 3
3 5 1
4 6 6
5 6 6

Output:

f[1, 2] = 5
f[1, 3] = 4
f[2, 4] = 3
f[2, 5] = 2
f[3, 4] = 3
f[3, 5] = 1
f[4, 6] = 6
f[5, 6] = 3
Max Flow: 9
 0  5  4  0  0  0 
-5  0  0  3  2  0 
-4  0  0  3  1  0 
 0 -3 -3  0  0  6 
 0 -2 -1  0  0  3 
 0  0  0 -6 -3  0 

Code: Pascal

// Finding the Maximum Flow using Ford-Fulkerson Algorithm
const fi = 'MAXFLOW.INP';
      fo = 'MAXFLOW.OUT';
      max = 1000;
type TCapacities = array [1..max, 1..max] of integer;
var c: TCapacities;
    f: TCapacities;
    Trace: array [1..max] of integer;
    n, s, t: integer;

    procedure Enter;
    var m, i, u, v: integer;
        f2: text;
    begin
        assign(f2, fi); reset(f2);
        fillchar(c, sizeof(c), 0);


        readln(f2, n, m, s, t);
        for i:= 1 to m do readln(f2, u, v, c[u, v]);
        close(f2);
    end;

    function FindPath: Boolean;
    var u, v: integer;
        Queue: array[1..max] of integer;
        Front, Rear: integer;
    begin
        fillchar(Trace, sizeof(Trace), 0);
        Front:= 1; Rear:= 1;
        Queue[1]:= s;
        Trace[s]:= n+1;
        repeat
                u:= Queue[Front];
                Inc(Front);

                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(Rear);
                        Queue[Rear]:= v;
                    end;
        until Front > Rear;
        FindPath:= false;
    end;

    procedure IncFlow;
    var Delta, u, v: integer;
    begin
        Delta:= MaxInt;
        v:= t;
        repeat
                u:= Trace[v];
                if c[u, v] - f[u, v] < Delta then Delta:= c[u, v] - f[u, v];
                v:= u;
        until v = s;

        v:= t;
        repeat
                u:= Trace[v];

                f[u, v]:= f[u, v] + Delta;
                f[v, u]:= f[v, u] - Delta;

                v:= u;
        until v = s;
    end;

    procedure PrintResult;
    var u, v: integer;
        m: integer;
        f2: text;
    begin
        assign(f2, fo); rewrite(f2);
        m:= 0;
        for u:= 1 to n do
            for v:= 1 to n do
                if f[u, v] > 0 then
                begin
                        writeln(f2, 'f[', u, ', ', v, '] = ', f[u, v]);
                        if u = s then m:= m + f[s, v];
                end;
        writeln(f2, 'Max Flow: ', m);
        for u:= 1 to n do
        begin
                for v:= 1 to n do write(f2, f[u, v]:2, ' ');
                writeln(f2);


        end;
        close(f2);
    end;


BEGIN
        Enter;
        fillchar(f, sizeof(f), 0);
        repeat
                if not FindPath then break;
                IncFlow;
        until false;
        PrintResult;
END.

6 8 1 6
1 2 5
1 3 5
2 4 6
2 5 3
3 4 3
3 5 1
4 6 6
5 6 6

One Response to “Luồng cực đại, using Ford-Fulkerson Algorithm”

  1. Họ Kiều Tên Sứ Says:

    bài này có hàm C không anh


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: