Category Archives: DefaultCategory

POJ 1088（滑雪）

Posted on by

标准记忆化搜索 模板题

Program P1088;
var
   ans,n,m,i,j:longint;
   a,f:array[0..101,0..101] of longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function dfs(x,y:longint):longint;
var
   i,j:longint;
begin
   if f[x,y]>0 then exit(f[x,y]);
   dfs:=0;
   if a[x-1,y]<a[x,y] then dfs:=max(dfs,dfs(x-1,y)+1);
   if a[x+1,y]<a[x,y] then dfs:=max(dfs,dfs(x+1,y)+1);
   if a[x,y-1]<a[x,y] then dfs:=max(dfs,dfs(x,y-1)+1);
   if a[x,y+1]<a[x,y] then dfs:=max(dfs,dfs(x,y+1)+1);
   f[x,y]:=dfs;
end;
begin
   read(n,m);
   fillchar(a,sizeof(a),127);
   for i:=1 to n do
      for j:=1 to m do
         read(a[i,j]);
   fillchar(f,sizeof(f),0);
   ans:=0;

   for i:=1 to n do
      for j:=1 to m do
      begin
         if f[i,j]=0 then ans:=max(ans,dfs(i,j));
      end;
   writeln(ans+1);
end.

POJ 1830（位运算+双向DFS）

Posted on by

此题也可用GE做，可是我不会矩阵乘法……

Program P1830;
const
   maxn=28;
   maxf=100007;
   none=-2139062144;
var
   ans,tt,n,i,j,s,t,mid:longint;
   b:array[1..29] of longint;
   h,num:array[0..maxf] of longint;

function hash(x:longint):longint;
var
   i,j:longint;
begin
   hash:=x mod maxf;
   while (num[hash]<>x) and (num[hash]<>none) do
   begin
      hash:=(hash+1) mod maxf;
   end;
   num[hash]:=x;
   exit(hash);
end;
procedure dfs(x,l:longint);
var
   i,j:longint;
begin
   if l=mid+1 then
   begin
      inc(h[hash(x)]);
      exit;
   end;
   for i:=l to mid do
      dfs(x xor b[i],i+1);
   dfs(x,mid+1);

end;
procedure find(x,l:longint);
var
   i,j:longint;
begin
   if l=n+1 then
   begin
      inc(ans,h[hash(x)]);
      exit;
   end;
   for i:=l to n do
      find(x xor b[i],i+1);
   find(x,n+1);

end;

begin
   read(tt);
   while (tt>0) do
   begin
      ans:=0;
      fillchar(b,sizeof(b),0);
      fillchar(num,sizeof(num),128);
      fillchar(h,sizeof(h),0);

      read(n);
      s:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(s,1 shl (i-1));
      end;
      t:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(t,1 shl (i-1));
      end;
      while (true) do
      begin
         read(i,j);
         if (i=0) and (j=0) then break;
         inc(b[i],1 shl (j-1));
      end;
      for i:=1 to n do inc(b[i],1 shl (i-1));
      mid:=n shr 1;
      dfs(s,1);
      find(t,mid+1);
      if ans=0 then writeln('Oh,it''s impossible~!!') else
      writeln(ans);
      dec(tt);
   end;
end.

POJ 1276(多重背包）

Posted on by

RT

count 表示 第i种面额在f[j] 放的数量

Program P1276;
const
   maxn=20;
   maxcash=1000000;
var
   cash,n,i,j:longint;
   cost,d:array[1..maxn] of longint;
   f,count:array[0..maxcash] of longint;
begin
   while not seekeof do
   begin
      read(cash,n);
      for i:=1 to n do read(d[i],cost[i]);
      fillchar(f,sizeof(f),0);
      for i:=1 to n do
      begin
         fillchar(count,sizeof(count),0);
         for j:=cost[i] to cash do
         begin
            if (f[j]<f[j-cost[i]]+cost[i]) and (count[j-cost[i]]<d[i]) then
            begin
               f[j]:=f[j-cost[i]]+cost[i];
               count[j]:=count[j-cost[i]]+1;
            end;
         end;
      end;

      writeln(f[cash]);
   end;
end.

POJ 3169(带起点的拆分约束）

Posted on by

这次的拆分约束有明显的起点。

拆分等式 Xb-Xa<=C

     Xa-Xb<=-C

Program P3169;
const
   maxml=10000;
   maxn=1000;
var
   n,ml,md,i,j:longint;
   a,b:array[1..maxml,1..3] of longint;
   d:array[0..maxn] of longint;
   flag:boolean;
procedure relax(v,u,w:longint);
begin
   if d[v]>d[u]+w then
   begin
      d[v]:=d[u]+w;
      flag:=true;
   end;
end;
procedure bellman_ford;
var
   i,j,k:longint;
begin
   fillchar(d,sizeof(d),127);
   d[1]:=0;
   for k:=1 to ml+md do
   begin
      flag:=false;
      for i:=1 to ml do
      begin
         relax(a[i,2],a[i,1],a[i,3]);
      end;
      for i:=1 to md do
      begin
         relax(b[i,1],b[i,2],-b[i,3]);
      end;
      if not(flag) then break;
   end;
   if flag then writeln('-1')
   else if d[n]=2139062143 then writeln('-2')
   else writeln(d[n]);



end;
begin
   read(n,ml,md);
   for i:=1 to ml do
   begin
      read(a[i,1],a[i,2],a[i,3]);
   end;
   for i:=1 to md do
   begin
      read(b[i,1],b[i,2],b[i,3]);
   end;
   bellman_ford;
end.

POJ 2942（Tarjen的点双连通分量+交叉染色法）

Posted on by

这题是点双连通分量，我一开始写成边的……

首先点双连通分量可能重叠……(1,2) (2,3) (3,1) (3,4) (4,5) (5,6) (3.6)

这时有（1，2，3）和（3，4，5，6）两组双连通分量

故一定要在Tarjen里判……另外Stack存边时注意特判(Stack不能为空）

当dfs[k]<=low[i] 时 就找到了点双连通分量 （这是点双连通）

请注意在推送（k，i）后遍历得到的一堆边(包括（k，i）)组成了一组点双连通分量

两个重要定理：

（1）       如果一个双连通分量内的某些顶点在一个奇圈中（即双连通分量含有奇圈），那么这个双连通分量的其他顶点也在某个奇圈中；

（2）       如果一个双连通分量含有奇圈，则他必定不是一个二分图。反过来也成立，这是一个充要条件。

Program P2942;
const
   maxn=1050;
   maxm=1000000;
Var
   n,m,i,j,x,y:longint;
   b:array[1..maxn,1..maxn] of boolean;

   color,c,dfs,low:array[1..maxn] of longint;

   attend,flag:array[1..maxn] of boolean;

   size,time,totssc:longint;

   stack:array[0..maxm,1..2] of longint;

function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function is_Binary(k,col:longint):boolean;
var
   i,j:longint;
begin
   color[k]:=col;
   for i:=1 to n do
      if (flag[i]) and (b[k,i]) then
      begin
         if color[i]=0 then
         begin
            if not(is_binary(i,3-col)) then exit(false);
         end
         else
         if color[k]=color[i] then exit(false);
      end;

   exit(true);
end;

procedure tarjen(k,father:longint);
var
   i,j:longint;
begin
   inc(time);
   dfs[k]:=time;
   low[k]:=time;

   c[k]:=1;
   for i:=1 to n do
      if (b[k,i]) and (dfs[k]>dfs[i]) and (i<>father) then
      begin
         if dfs[i]=0 then
         begin

         inc(size);
         stack[size,1]:=k;
         stack[size,2]:=i;



         tarjen(i,k);
         low[k]:=min(low[k],low[i]);

         if dfs[k]<=low[i] then
         begin
            fillchar(flag,sizeof(flag),false);
            fillchar(color,sizeof(color),false);
            while (size>0) do
            begin
               flag[stack[size,1]]:=true;
               flag[stack[size,2]]:=true;
               dec(size);
               if (stack[size+1,1]=k) and (stack[size+1,2]=i) then break;

            end;

            if not(is_binary(k,1)) then
            begin
               for j:=1 to n do
                  if flag[j] then attend[j]:=true;


            end;


         end;


         end
         else
         if c[i]=1 then low[k]:=min(low[k],dfs[i]);
      end;





   c[k]:=2;

end;


function main:longint;
var
   i,j,tot:longint;
begin
   fillchar(dfs,sizeof(dfs),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(attend,sizeof(attend),false);
   fillchar(flag,sizeof(flag),false);
   fillchar(color,sizeof(color),0);
   fillchar(stack,sizeof(stack),0);
   size:=0;time:=0;
   for i:=1 to n do
      if (dfs[i]=0) then
      begin
          tarjen(i,0);
      end;

   tot:=0;
   for i:=1 to n do if attend[i] then inc(tot);
   exit(n-tot);

end;

begin
   while not seekeof do
   begin
      read(n,m);
      if (n=0) and (m=0) then break;
      fillchar(b,sizeof(b),true);
      for i:=1 to n do b[i,i]:=false;
      for i:=1 to m do
      begin
         read(x,y);
         b[x,y]:=false;
         b[y,x]:=false;
      end;
      writeln(main);
   end;
end.

POJ 2186（有向图的强连通分量）

Posted on by

题目大意：给有向图G，求图G中有多少点能从所有起点到达

暴搜必T，故本题需要用Tarjen求有向图的强连通分量。

缩点后得DAG（若有环则属同一强连通分量）

由于无环，故这图为树或树的森林

先判断图是否连通，若为森林则无解

否则，判定每个SSC是否有连出的边（由于图无环,故连出的边上的点无法回去）

答案即为出度为0的连通分量上的点

如果不止一个这样的点，则不同的点无法互相到达

Program P2186;
const
   maxn=10000;
   maxm=50000;
var
   head,edge,tail:array[1..maxm] of longint;
   sizeedge:longint;


   n,m,i,j,x,y:longint;
   ssc,c,dfs,low,outdegree,stack:array[1..maxn] of longint;
   time,size:longint;
   totssc:longint;

procedure addedge(u,v:longint);
begin
   inc(sizeedge);
   edge[sizeedge]:=v;
   tail[sizeedge]:=head[u];
   head[u]:=sizeedge;

end;


function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure tarjen(k,father:longint);
var
   i,j,p:longint;
begin
   inc(time);
   dfs[k]:=time;low[k]:=time;
   c[k]:=1;
   inc(size);stack[size]:=k;

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

      if (dfs[k]>dfs[i]) then
      begin
         if c[i]=0 then
         begin
            tarjen(i,k);
            low[k]:=min(low[k],low[i]);
         end
         else if c[i]=1 then low[k]:=min(low[k],dfs[i]);
      end;
      p:=tail[p];

   end;
   if low[k]=dfs[k] then
   begin
      inc(totssc);
      repeat
         i:=stack[size];
         dec(size);
         c[i]:=2;
         ssc[i]:=totssc;
      until ((size=0) or (i=k));

   end;
end;
function main:longint;
var
   i,j,tot,node,p:longint;
begin
   fillchar(dfs,sizeof(dfs),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(outdegree,sizeof(outdegree),0);
   time:=0;
   totssc:=0;
   for i:=1 to n do
      if (dfs[i]=0) then
      begin
         fillchar(stack,sizeof(stack),0);
         size:=0;
         tarjen(i,0);
      end;

   for i:=1 to n do
   begin
      p:=head[i];
      while (p<>0) do
      begin
         j:=edge[p];

         if (ssc[i]<>ssc[j]) then
         begin
            inc(outdegree[ssc[i]]);
         end;
         p:=tail[p];


      end;
   end;

   node:=0;
   for i:=1 to totssc do
      if outdegree[i]=0 then
      begin
         if node<>0 then exit(0);
         node:=i;
      end;
   tot:=0;
   for i:=1 to n do
      if ssc[i]=node then inc(tot);
   exit(tot);


end;
begin
   sizeedge:=0;
   fillchar(head,sizeof(head),0);
   fillchar(tail,sizeof(tail),0);
   fillchar(edge,sizeof(edge),0);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      addedge(x,y);
   end;
   writeln(main);
end.

HYSBZ 1048(记忆化搜索）

Posted on by

把一个大矩阵分割成n个矩阵，使它们的方差最小。

g[i,j,k,l,path]表示（i,j） 到 （k,l) 的矩阵分割成path个的最小方差，然后暴力搜索+记忆化

O（n^5) (n<=10) ,无压力水过。

Program b;
const
   maxn=10;
var
   n,m,i,j,k,l,deltax,r:longint;
   delta:double;
   f:array[1..maxn,1..maxn] of longint;
   sum:array[1..maxn,1..maxn,1..maxn,1..maxn] of double;
   g:array[1..maxn,1..maxn,1..maxn,1..maxn,1..maxn] of double;
function min(a,b:double):double;
begin
   if a<b then exit(a) else exit(b);
end;
function dfs(x,y,k,l,path:longint):double;
var
   i,j:longint;
   ans:double;
begin
   if g[x,y,k,l,path]<>0 then exit(g[x,y,k,l,path]);

   if path=1 then
   begin
      g[x,y,k,l,1]:=sum[x,y,k,l]-delta;
      g[x,y,k,l,1]:=g[x,y,k,l,1]*g[x,y,k,l,1];

      exit(g[x,y,k,l,1]);
   end;
   ans:=maxlongint;




   for i:=x to k-1 do
      for j:=1 to path-1 do
         ans:=min(ans,dfs(x,y,i,l,j)+dfs(i+1,y,k,l,path-j));
   for j:=y to l-1 do
      for i:=1 to path-1 do
         ans:=min(ans,dfs(x,y,k,j,i)+dfs(x,j+1,k,l,path-i));


   g[x,y,k,l,path]:=ans;
   exit(ans);

end;
begin
   read(n,m,r);
   deltax:=0;
   for i:=1 to n do
      for j:=1 to m do
      begin
         read(f[i,j]);
         sum[i,j,i,j]:=f[i,j];
         inc(deltax,f[i,j]);

      end;



   delta:=deltax/r;
   for i:=1 to n do
      for j:=1 to m do
      begin
         for k:=i+1 to n do
         begin
            sum[i,j,k,j]:=sum[i,j,k-1,j]+f[k,j];
         end;
         for l:=j+1 to m do
         begin
            sum[i,j,i,l]:=sum[i,j,i,l-1]+f[i,l];
         end;

         for k:=i+1 to n do
            for l:=j+1 to n do
            begin
               sum[i,j,k,l]:=sum[i,j,k-1,l]+sum[i,j,k,l-1]-sum[i,j,k-1,l-1]+f[k,l];
           end;
      end;
   fillchar(g,sizeof(g),0);





   writeln(sqrt(dfs(1,1,n,m,r)/r):2:2);


end.

·

POJ 3177(带重边的连通图的双连通分量）

Posted on by

题目大意：求带重边的连通图至少加几条边变成双连通图

POJ 3352
+重边

用邻接矩阵的表示无压力

Program P3177;
const
   maxn=1000;
   maxm=1000;
var
   n,m,i,j,x,y:longint;
   b:array[1..maxn,1..maxn] of boolean;

   indegree,c,a,low:array[1..maxn] of longint;
   time:longint;
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 tarjan(k,father:longint);
var
   i,j:longint;
begin
   inc(time);
   a[k]:=time;
   low[k]:=time;


   c[k]:=1;

   for i:=1 to n do
   begin
      if (b[i,k]) and (i<>father) and (a[i]<a[k]) then
      begin


         if c[i]=0 then
         begin
            tarjan(i,k);
            low[k]:=min(low[k],low[i]);
         end;
         if (c[i]=1) and (i<>father) then
         begin
            low[k]:=min(low[k],a[i]);
         end;


      end;
   end;




   c[k]:=2;



end;

procedure main;
var
   i,j,tot:longint;
begin
   fillchar(a,sizeof(a),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(indegree,sizeof(indegree),0);

   time:=0;
   tarjan(1,0);

   for i:=1 to n do
      for j:=i+1 to n do
         if (low[i]<>low[j]) and (b[i,j]) then
         begin
            inc(indegree[low[i]]);
            inc(indegree[low[j]]);
         end;
   tot:=0;
   for i:=1 to n do if indegree[i]=1 then inc(tot);
   writeln((tot+1) div 2);

end;

begin
   fillchar(b,sizeof(b),false);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      b[x,y]:=true;
      b[y,x]:=true;
   end;
   main;
end.

POJ 3352(Tarjen中Low的性质）

Posted on by

这题做了半天……结果发现自己缩点错了……

言归正传，这题给了一个无向图G，求添加几条边后双连通……

做了一上午Tarjen不对……Low就是不满足性质（后来发现这是无向图的，要用有向图版本……——用有向图法做无向图……）

终于……做完了（请忽略Stack，我最后索性直接用Low值了……勉强算hash？）

Program P3352;
const
   maxn=1000;
   maxm=1000;
var
   n,m,i,j,x,y:longint;
   b:array[1..maxn,1..maxn] of boolean;

   indegree,c,stack,a,low:array[1..maxn] of longint;
   size,time:longint;

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 swap(a,b:longint);
var
   p:longint;
begin
   p:=a;
   a:=b;
   b:=p;
end;

procedure tarjan(k,father{,deep}:longint);
var
   i,j:longint;
begin

   inc(size);
   stack[size]:=k;     //for suo_dian^_^
   inc(time);
   a[k]:=time;
   low[k]:=time;
 {
   low[k]:=deep;
   a[k]:=deep;
  }

   c[k]:=1;

   for i:=1 to n do
   begin
      if (b[i,k]) and (i<>father) and (a[i]<a[k]) then
      begin


         if c[i]=0 then
         begin
            tarjan(i,k{,deep+1});
            low[k]:=min(low[k],low[i]);
         end;
         if (c[i]=1) and (i<>father) then
         begin
            low[k]:=min(low[k],a[i]);
         end;


      end;
   end;




   c[k]:=2;



end;

procedure main;
var
   i,j,tot:longint;
begin
   fillchar(stack,sizeof(stack),0);
   fillchar(a,sizeof(a),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(indegree,sizeof(indegree),0);

   size:=0;time:=0;
   tarjan(1,0{,1});

   for i:=1 to n do
      for j:=i+1 to n do
         if (low[i]<>low[j]) and (b[i,j]) then
         begin
            inc(indegree[low[i]]);
            inc(indegree[low[j]]);
         end;
   tot:=0;
   for i:=1 to n do if indegree[i]=1 then inc(tot);
   writeln((tot+1) div 2);

end;

begin
while not seekeof do
begin
   fillchar(b,sizeof(b),false);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      b[x,y]:=true;
      b[y,x]:=true;
   end;
   main;
end;
end.

POJ 2010(二叉堆-入门）

Posted on by

好像这题二分也可以做……

话说这年头写堆都不用Heapify 函数的？

Program P2010;
const
   maxc=100000;
   maxn=19999;
   maxaid=100000;
   maxf=2000000000;
type
   node=record
        a,b:longint;
        end;
   heap=record
        size:longint;
        d:array[1..maxc] of longint;
        end;
var
   n,c,f,i,j:longint;
   a:array[1..maxc] of node;
   h:heap;
   before,after:array[1..maxc] of longint;


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

         inc(i);dec(j);
      end;


   until i>j;

   if l<j then qsort(l,j);
   if i<r then qsort(i,r);


end;

procedure push(t:longint);
var
   i:longint;
begin
   with h do
   begin
      inc(size);
      d[size]:=t;
      i:=size;
      while i>1 do
      begin
         if d[i shr 1]>=d[i] then break;
         swap(d[i shr 1],d[i]);
         i:=i shr 1;
      end;
   end;
end;
procedure pop;
var
   i,j:longint;
begin
   with h do
   begin
      d[1]:=d[size];
      dec(size);
      i:=1;
      while i shl 1<=size do
      begin
         j:=i shl 1;
         if (j<size) then if d[j]<d[j+1] then inc(j);
         if d[j]<d[i] then break;
         swap(d[i],d[j]);
         i:=j;
      end;
   end;

end;
function front:longint;
begin
   exit(h.d[1]);
end;
function main:longint;
var
   i,j,mid,ans,num:longint;
begin
   mid:=n div 2;
   fillchar(before,sizeof(before),0);
   fillchar(after,sizeof(after),0);
   for i:=1 to mid do
   begin
      push(a[i].b);
      inc(before[mid+1],a[i].b);
   end;
   for i:=mid+2 to c-mid do
   begin
      if front<=a[i-1].b then before[i]:=before[i-1]
      else
      begin
         before[i]:=before[i-1]-front+a[i-1].b;
         pop;
         push(a[i-1].b);
      end;
   end;
   fillchar(h,sizeof(h),0);
   for i:=c downto c-mid+1 do
   begin
      push(a[i].b);
      inc(after[c-mid],a[i].b);
   end;
   for i:=c-mid-1 downto mid+1 do
   begin
      if front<=a[i+1].b then after[i]:=after[i+1]
      else
      begin
         after[i]:=after[i+1]-front+a[i+1].b;
         pop;
         push(a[i+1].b);
      end;
   end;
   ans:=f+1;
   num:=-1;
   for i:=mid+1 to c-mid do
      if f>=before[i]+after[i]+a[i].b then
      begin
         num:=i;
      end;
   if num=-1 then exit(-1);
   exit(a[num].a);
end;
begin
   while not seekeof do
   begin
      fillchar(h,sizeof(h),0);
      read(N,C,F);
      for i:=1 to c do read(a[i].a,a[i].b);
      qsort(1,c);
      writeln(main);

   end;
end.