FWATER - Tưới nước đồng cỏ

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program FWATER;
  Const
    input  = '';
    output = '';
    maxn = 300;
    maxc = 100000000;
  Var
    a: array[0..maxn,0..maxn] of integer;
    d,trace: array[0..maxn] of integer;
    free: array[0..maxn] of boolean;
    w: array[1..maxn] of integer;
    n: integer;

Procedure init;
  Var
    f: text;
    i,j: integer;
  Begin
    Assign(f, input);
      Reset(f);

    Readln(f, n);
    For i:= 1 to n do
      Begin
        readln(f, a[0,i]);
        a[i,0]:= a[0,i];
      End;

    For i:= 1 to n do
      For j:= 1 to n do read(f, a[i,j]);

    Close(f);
  End;

Procedure Prim;
  Var
    u,v,i,k,min: integer;
  Begin
    Fillchar(free, sizeof(free), true);

    For i:= 1 to n do d[i]:= maxc;
    d[0]:= 0;

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

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

        free[u]:= false;
        For v:= 0 to n do
          if free[v] and (d[v] > a[u,v]) then
            Begin
              d[v]:= a[u,v];
              trace[v]:= u;
            End;
      End;
  End;

Procedure printresult;
  Var
    f: text;
    i,res: integer;
  Begin
    Assign(f, output);
      Rewrite(f);

      res:= 0;
      For i:= 1 to n do res:= res + a[trace[i],i];

      Writeln(f, res);
    Close(f);
  End;

Begin
  init;
  Prim;
  printresult;
End.

Download