Список литературы

1. Бройдо, В. Л. Вычислительные системы, сети и телекоммуникации / В. Л. Бройдо. – СПб. : Питер, 2002. – 688 с.

2. Телекоммуникационные системы и сети / Г.П. Катунин, Г.В. Мамчев и др. – М. : Телеком, 2004. – 672 с.

3. Столингс, В. Компьютерные системы передачи данных / В. Столингс. – М. : Вильямс, 2002. – 928 с.

4. Олифер, В. Г. Основы сетей передачи данных / В. Г. Олифер, Н. А. Олифер. – М. : ИНТУИТ.РУ,2003. – 248 с.

5. Новиков, Ю. Персональные компьютеры: аппаратура, системы, Интернет / Ю. Новиков, А. Черепанов. – СПб. : Питер, 2001. – 464 с.

6. Рудометов, Е. Устройство мультимедийного компьютера / Е. Рудометов, В. Рудометов. – СПб.: Питер, 2001. – 512 с.: ил.

Приложение а ( справочное ) Листинг кода

program Project2;

{$APPTYPE CONSOLE}

uses

SysUtils;

const maxn = 500;

var n: integer;

g: array [0..500, 0..500] of integer;

v: array[0..500, 0..500] of integer;

best_cost: integer;

best_cut : integer;

i,j: integer;

procedure mincut;

var i, ph, it, sel, k, j, prev: integer;

w: array [0..500] of integer;

exist, in_a: array [0..500] of boolean;

begin

for i := 0 to n-1 do

for j := 0 to n-1 do

if (i = j) then v[i][j] := 1;

for i := 0 to maxn do

exist[i] := true;

for ph := 0 to n-1 do

begin

for i := 0 to maxn do

begin

in_a[i] := false;

w[i] := 0;

end;

prev := 0;

for it := 0 to n-ph-1 do

begin

sel := -1;

for i := 0 to n-1 do

if (exist[i]) AND not (in_a[i]) AND ((sel = -1) OR (w[i] > w[sel])) then

sel := i;

if (it = n-ph-1) then

begin

if (w[sel] < best_cost) and (sel > 0) then

begin

best_cost := w[sel];

best_cut := sel;

INC(k);

end;

for i := 0 to n-1 do

if v[sel][i] = 1 then

v[prev][i] := 1;

for j := 0 to n-1 do

begin

g[j][prev] := g[j][prev] + g[j][sel];

end;

exist[sel] := false;

end

else

begin

in_a[sel] := true;

for j := 0 to n-1 do

w[j] := w[j] + g[sel][j];

prev := sel;

end;

end;

end;

end;

begin

best_cost := 1000000000;

assign(input, 'input.txt');

assign (output, 'output.txt');

readln(n);

for i := 0 to n-1 do

begin

for j := 0 to n-1 do

begin

read(g[i][j]);

end;

readln;

end;

mincut;

write('Стоимость минимального разреза = ');

writeln(best_cost);

write('Вершины минимального разреза: ');

for i := 0 to n-1 do

if v[best_cut][i] = 1 then

write(i,' ');

readln;

end. program Project2;

{$APPTYPE CONSOLE}

uses

SysUtils;

const maxn = 500;

var n: integer;

g: array [0..500, 0..500] of integer;

v: array[0..500, 0..500] of integer;

best_cost: integer;

best_cut : integer;

i,j: integer;

procedure mincut;

var i, ph, it, sel, k, j, prev: integer;

w: array [0..500] of integer;

exist, in_a: array [0..500] of boolean;

begin

for i := 0 to n-1 do

for j := 0 to n-1 do

if (i = j) then v[i][j] := 1;

for i := 0 to maxn do

exist[i] := true;

for ph := 0 to n-1 do

begin

for i := 0 to maxn do

begin

in_a[i] := false;

w[i] := 0;

end;

prev := 0;

for it := 0 to n-ph-1 do

begin

sel := -1;

for i := 0 to n-1 do

if (exist[i]) AND not (in_a[i]) AND ((sel = -1) OR (w[i] > w[sel])) then

sel := i;

if (it = n-ph-1) then

begin

if (w[sel] < best_cost) and (sel > 0) then

begin

best_cost := w[sel];

best_cut := sel;

INC(k);

end;

for i := 0 to n-1 do

if v[sel][i] = 1 then

v[prev][i] := 1;

for j := 0 to n-1 do

begin

g[j][prev] := g[j][prev] + g[j][sel];

end;

exist[sel] := false;

end

else

begin

in_a[sel] := true;

for j := 0 to n-1 do

w[j] := w[j] + g[sel][j];

prev := sel;

end;

end;

end;

end;

begin

best_cost := 1000000000;

assign(input, 'input.txt');

assign (output, 'output.txt');

readln(n);

for i := 0 to n-1 do

begin

for j := 0 to n-1 do

begin

read(g[i][j]);

end;

readln;

end;

mincut;

write('Стоимость минимального разреза = ');

writeln(best_cost);

write('Вершины минимального разреза: ');

for i := 0 to n-1 do

if v[best_cut][i] = 1 then

write(i,' ');

readln;

end.