记录编号	135961	评测结果	AAAAAAAAAA
题目名称	最优布线问题	最终得分	100
用户昵称	safhsdajkfhsad	是否通过	通过
代码语言	Pascal	运行时间	1.555 s
提交时间	2014-11-01 22:13:35	内存使用	13.90 MiB

const
  maxnum=1200000;
type
  tvnode=record
    x,y,v:longint;
  end;
var
  dav:array[0..maxnum] of tvnode;
  vnum,i,j,n,vtem,vans,vrushu:longint;
  dazuxian:array[1..1500] of longint;

procedure gcqsort(st,en:longint);
  var
    i,j,mid:longint;
    tem:tvnode;
  begin
    mid:=dav[(st+en) div 2].v;
    i:=st;
    j:=en;
    while (i<=j) do
      begin
        while (dav[i].v<mid) do
          inc(i);
        while (dav[j].v>mid) do
          dec(j);
        if (i<=j) then
          begin
            tem:=dav[i];
            dav[i]:=dav[j];
            dav[j]:=tem;
            inc(i);
            dec(j);
          end;
      end;

    if (st<j) then
      gcqsort(st,j);
    if (i<en) then
      gcqsort(i,en);
  end;

function hsfd(x:longint):longint;
  begin
    if (x<>dazuxian[x]) then
     dazuxian[x]:=(hsfd(dazuxian[x]));

    hsfd:=dazuxian[x];
  end;

procedure gcunion(x,y:longint);
  begin
    dazuxian[hsfd(x)]:=hsfd(dazuxian[y]);
  end;

begin
  assign(input,'wire.in');
  reset(input);
  assign(output,'wire.out');
  rewrite(output);
  readln(n);
  vnum:=0;
  for i:=1 to n do
    for j:=1 to n do
      begin
        read(vtem);
        if ((vtem=0)or(j>=i)) then
          continue;
        inc(vnum);
        dav[vnum].v:=vtem;
        dav[vnum].x:=i;
        dav[vnum].y:=j;
      end;

  gcqsort(1,vnum);
  {
  for i:=1 to vnum do
    begin
      write(dav[i].v,' ');
    end;
    writeln;
  }
  for i:=1 to n do
    dazuxian[i]:=i;

  vans:=0;
  vrushu:=1;
  vnum:=0;
  while (vrushu<n) do
    begin
      inc(vnum);
      if (hsfd(dav[vnum].x) <> (hsfd(dav[vnum].y))) then
        begin
          inc(vrushu);
          inc(vans,dav[vnum].v);
          gcunion(dav[vnum].x,dav[vnum].y);
        end;
    end;

  writeln(vans);
  close(input);
  close(output);
end.