NKCITY - Xây dựng thành phố

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program NKCITY;
        Const
                input  = '';
                output = '';
        Var
                c: array[1..1000,1..1000] of integer;
                d: array[1..1000] of integer;
             free: array[1..1000] of boolean;
              n,m: integer;

Procedure LoadGraph;
          Var
                        f: text;
                  i,j,u,v: integer;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, n, m);

                For u:= 1 to n do
                  For v:= 1 to n do
                    if u = v then c[u,v]:= 0 else c[u,v]:= 1000000000;

                For i:= 1 to m do
                    Begin
                        Readln(f, u, v, c[u,v]);
                        c[v,u]:= c[u,v];
                    End;

                Close(f);
          End;

Procedure Prim;
          Var
                          f: text;
                     maxlen: integer;
                u,i,min,v,k: integer;
          Begin
                d[1]:= 0;
                For i:= 2 to n do d[i]:= 1000000000;
                maxlen:= 0;

                FIllchar(free, sizeof(free), true);

                For k:= 1 to n do
                    Begin
                        u:= 0;
                        min:= 1000000000;

                        For i:= 1 to n do
                                if free[i] and (d[i] < min) then
                                        Begin
                                                u:= i;
                                                min:= d[i];
                                        End;
                        If maxlen < min then maxlen:= min;

                        free[u]:= false;
                        For v:= 1 to n do
                            If free[v] and (d[v] > c[u,v])
                                       then d[v]:= c[u,v];
                    End;

                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, maxlen);
                Close(f);
          End;

Begin
        LoadGraph;
        Prim;
End.

Download