Daily Archives: 26 8 月, 2012

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.