POJ 2110(最小生成树）

这题的思路就是找一个范围，看看这个范围是否可行

主流是二分Ans，我是先把点排序，求最小生成树检查首位的

Program P2110;
type
   ed=record
      u,v,w:longint;
      end;
var
   a:array[1..120,1..120] of longint;
   edge:array[0..30000] of ed;
   n,i,j,size,ans:longint;
   now:longint;
   father:array[0..10001] of longint;
   b:array[0..121,0..121] of boolean;
procedure add(u,v,w:longint);
begin
   inc(size);
   edge[size].u:=u;
   edge[size].v:=v;
   edge[size].w:=w;

end;
procedure qsort(l,r:longint);
var
   i,j,m:longint;
   p:ed;
begin
   i:=l;
   j:=r;
   m:=edge[(l+r) shr 1].w;
   repeat
      while edge[i].w<m do inc(i);
      while edge[j].w>m do dec(j);
      if i<=j then
      begin
         p:=edge[i];
         edge[i]:=edge[j];
         edge[j]:=p;
         inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);



end;
function getfather(x:longint):longint;
begin
   if x=father[x] then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
function hash(x,y:longint):longint;
begin
  exit((x-1)*n+y);
end;
begin
   size:=0;
   read(n);
   for i:=1 to n do
      for j:=1 to n do
      begin
         read(a[i,j]);
         add(i,j,a[i,j]);
      end;

  // (0,n*n)
   qsort(1,size);


   edge[0].w:=edge[1].w-1;
   ans:=110;
   //                 writeln;
   for i:=1 to size do
   begin

      if edge[i].w=edge[i-1].w then continue;
      for j:=0 to n*n do father[j]:=j;
      fillchar(b,sizeof(b),false);
      for j:=i to size do
      begin
         b[edge[j].u,edge[j].v]:=true;
         now:=hash(edge[j].u,edge[j].v);

         if b[edge[j].u-1,edge[j].v] then
            if getfather(now)<>getfather(now-n) then
            begin
               father[father[now]]:=father[father[now-n]];
               if getfather(0)=getfather(n*n) then break;
            end;

         if b[edge[j].u+1,edge[j].v] then
            if getfather(now)<>getfather(now+n) then
            begin
               father[father[now]]:=father[father[now+n]];
               if getfather(0)=getfather(n*n) then break;
            end;

         if b[edge[j].u,edge[j].v+1] then
            if getfather(now)<>getfather(now+1) then
            begin
               father[father[now]]:=father[father[now+1]];
               if getfather(0)=getfather(n*n) then break;
            end;

         if b[edge[j].u,edge[j].v-1] then
            if getfather(now)<>getfather(now-1) then
            begin
               father[father[now]]:=father[father[now-1]];
               if getfather(0)=getfather(n*n) then break;
            end;



         if getfather(1)=getfather(n*n) then break;

      end;



      if getfather(1)<>getfather(n*n) then break;
      if ans>edge[j].w-edge[i].w then ans:=edge[j].w-edge[i].w;


   end;
   writeln(ans);



end.