km_feszitofa.pas

Letöltés: km_feszitofa.pas

{$R+}
program feszitofa;

uses crt;

const N=40;
      H='network.txt';

type el = record h1,h2,ert:integer; end;

var i,j,eleklen,joeleklen,db,osszeg,x,y,nagyapa : longint;
    elekossz : longint;
    elek : array[1..N*N] of el;
    joelek : array[1..N*N] of el;
    apa : array[1..N] of integer;
    be : text;

procedure rendezel();
var cser : el;
    
begin
    for i:=1 to eleklen do
        for j:=i to eleklen do begin
            if elek[j].ert<elek[i].ert then begin
                cser := elek[i];
                elek[i]:=elek[j];
                elek[j]:=cser;
                end;
            end;
    end;

function holvan(x:integer):integer;
begin
    if apa[x]=x then begin
        holvan:=x;
        nagyapa:=x;
        end
    else
        holvan:=holvan(apa[x]);
        apa[x]:=nagyapa;
    end;

procedure unio(x,y:integer);
begin
    apa[x]:=apa[y];
    end;

BEGIN
    
    eleklen:=0;
    assign(be,H);
    reset(be);
    elekossz :=0;
    for i:=1 to N do begin
        for j:=1 to N do begin
            read(be,db);
            if (j>i-1) and (db<>-1) then begin
                eleklen:=eleklen+1;
                elek[eleklen].h1:=i;
                elek[eleklen].h2:=j;
                elek[eleklen].ert:=db;
                elekossz:= elekossz+db;
                end;
            end;
        readln(be);
        end;
    for i:=1 to N do
        apa[i]:=i;
    rendezel();
    db:=0;
    i:=1;
    osszeg:=0;
    joeleklen := 0;
    while db<N-1 do begin
        x:=elek[i].h1;
        y:=elek[i].h2;
        write(' <(',x,'-',holvan(x),',',y,'-',holvan(y),')> ');
        if holvan(x) <> holvan(y) then begin
            joeleklen := joeleklen + 1;
            joelek[joeleklen]:=elek[i];
            osszeg:=osszeg + elek[i].ert;
            db:=db+1;
            unio(holvan(x),holvan(y));
            end;
        i:=i+1;
        end;
    for i:=1 to joeleklen do
        write(' (',joelek[i].h1,',',joelek[i].h2,')',joelek[i].ert,' ');
    writeln(elekossz - osszeg,' ',elekossz,' ',osszeg);
    
    
END.