Daily Archives: 27 8 月, 2012

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.

·