Daily Archives: 25 8 月, 2012

POJ 1856(海战）

Posted on by

搜索 此题数据小，不需要状压

Program P1856;
var
   n,m,i,j,ans:longint;
   c:char;
   f:array[0..1010,0..1010] of boolean;
function find(x,y:longint):boolean;
var
   i,j,k,l:longint;
begin
   i:=x;j:=y;
   while f[x,j] do inc(j);
   dec(j);
   while f[i,y] do inc(i);
   dec(i);
   for k:=x to i do
      for l:=y to j do
      begin
         if not(f[k,l]) then exit(false);
         f[k,l]:=false;

      end;
   for k:=x-1 to i+1 do
      if f[k,j+1] or f[k,y-1] then exit(false);
   for l:=y to j do
      if f[i+1,l] or f[x-1,l] then exit(false);




   exit(true);



end;
function main:boolean;
var
   i,j:longint;
begin
   ans:=0;
   for i:=1 to n do
      for j:=1 to m do
         if f[i,j] then
         begin
            if not(find(i,j)) then exit(false)
            else inc(ans);
         end;

   exit(true);
end;
begin
   while not seekeof do
   begin
      fillchar(f,sizeof(f),false);
      readln(n,m);
      if (n+m=0) then break;
      for i:=1 to n do
      begin
         for j:=1 to m do
         begin
            read(c);
            if c='#' then f[i,j]:=true;

         end;
         readln;
      end;

      if main then writeln('There are ',ans,' ships.')
      else writeln('Bad placement.');
   end;
end.

POJ 1523（求割点）

Posted on by

求割点入门题！

……死调一下午+晚上才发现把‘node'打成’nodes'了……

Program P1523;
const
   maxedge=999000;
   maxn=10000;
var
   edge,tail:array[1..maxedge] of longint;
   size:longint;
   head:array[1..maxn] of longint;

   n,i,j,ans,k:longint;
   b,cut:array[1..maxn] of boolean;


   time,root:longint;
   a,d,ancestor,c:array[1..maxn] of longint;


procedure addedge(u,v:longint);
begin
   inc(size);
   edge[size]:=v;
   tail[size]:=head[u];
   head[u]:=size;
end;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure Dfs(k,father,deep:longint);
var
   i,j,p,tot:longint;
begin
   tot:=0;
   c[k]:=1;
   d[k]:=deep;
   ancestor[k]:=deep;

   p:=head[k];

   while (p>0) do
   begin
      i:=edge[p];

      if (i<>father) and (c[i]=1) then ancestor[k]:=min(ancestor[k],d[i]);

      if (c[i]=0) then
      begin
         dfs(i,k,deep+1);
         inc(tot);
         ancestor[k]:=min(ancestor[k],ancestor[i]);
         if (k=root) and (tot>=2) then cut[k]:=true;
         if (k<>root) and (ancestor[i]>=d[k]) then cut[k]:=true;

      end;



      p:=tail[p];
   end;

   c[k]:=2;
   inc(time);
   a[k]:=time;

end;
procedure Dfs2(k:longint);
var
   i,p:longint;
begin
   b[k]:=true;

   p:=head[k];

   while (p>0) do
   begin
      i:=edge[p];


      if not(b[i]) then
      begin
         dfs2(i);

      end;



      p:=tail[p];
   end;

end;

function main:boolean;
var
   i,j,p,ans:longint;
begin
   time:=0;
   main:=false;
   for i:=1 to maxn do
      if (head[i]>0) and (c[i]=0) then
      begin
        root:=i;
        dfs(root,0,1);
      end;



   for i:=1 to maxn do
      if cut[i] then
      begin
         main:=true;
         ans:=0;
         fillchar(b,sizeof(b),false);
         b[i]:=true;
         p:=head[i];
         while (p>0) do
         begin
            if not(b[edge[p]]) then
            begin
               dfs2(edge[p]);
               inc(ans);
            end;
            p:=tail[p];
         end;

         writeln('  SPF node ',i,' leaves ',ans,' subnets');

      end;






end;

begin
 {  assign(input,'p1523.in');
   reset(input);
    }
   k:=1;
   while not seekeof do
   begin
      size:=0;
      fillchar(head,sizeof(head),0);
      fillchar(edge,sizeof(edge),0);
      fillchar(tail,sizeof(tail),0);
      fillchar(cut,sizeof(cut),false);
      fillchar(c,sizeof(c),0);
      fillchar(d,sizeof(d),0);
      fillchar(ancestor,sizeof(ancestor),0);




      read(i);
      if i=0 then break;
      read(j);
      while (i>0) do
      begin
         addedge(i,j);
         addedge(j,i);
         read(i);
         if i=0 then break;
         read(j);
      end;
      ans:=0;
      writeln('Network #',k);

      if not(main) then writeln('  No SPF nodes');





      writeln;
      inc(k);
   end;
end.