【POJ3498】March of the Penguins（最大流，裂点）

题意：在靠近南极的某处，一些企鹅站在许多漂浮的冰块上。由于企鹅是群居动物，所以它们想要聚集到一起，在同一个冰块上。企鹅们不想把自己的身体弄湿，所以它们在冰块之间跳跃，但是它们的跳跃距离，有一个上限。
随着气温的升高，冰块开始融化，并出现了裂痕。而企鹅跳跃的压力，使得冰块的破裂加速。幸运的是，企鹅对冰块十分有研究，它们能知道每块冰块最多能承受多少次跳跃。对冰块的损害只在跳起的时候产生，而落地时并不对其产生伤害。
现在让你来帮助企鹅选择一个冰面使得它们可以聚集到一起。

第一行整数N，和浮点数D，表示冰块的数目和企鹅的最大跳跃距离。

(1≤N ≤100) (0 ≤D ≤100 000),
接下来N行，xi, yi, ni and mi,分别表示冰块的X和Y坐标，该冰块上的企鹅数目，以及还能承受起跳的次数。

输出所有可能的相聚冰块的编号，以0开始。如果不能相遇，输出-1。

思路：这道题是一年前上课最大流的例题，如果去年就拿了一等多好

考虑强行限制起跳次数很难，尝试裂点

将每块冰都裂成两个点(i,1),(i,2)

(i,1)-->(i,2)连流量为m[i]的边

对于原来在冰面上的企鹅，建立超级源S

s-->(i,1)连流量为n[i]的边

对于平面距离小于D的两点i,j

(i,2)-->(j,1)连流量为maxlongint的边

枚举(j,1)作为汇点判断最大流量是否>=企鹅总数即可

 var head,vet,next,gap,dis,len,c,fan,a,b,save:array[..]of longint;

     x,y:array[..]of double;

     num:array[..,..]of longint;

     n,m,qq,tot,i,j,ans,v,cas,s,source,src,st:longint;

     d:double;

 procedure add(a,b,c:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  len[tot]:=c;

  head[a]:=tot;

 end;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function dfs(u,aug:longint):longint;

 var e,v,flow,t,val:longint;

 begin

  if u=src then exit(aug);

  e:=head[u]; flow:=; val:=s-;

  while e<> do

  begin

   v:=vet[e];

   if len[e]> then

   begin

    if dis[u]=dis[v]+ then

    begin

     t:=dfs(v,min(len[e],aug-flow));

     len[e]:=len[e]-t;

     len[fan[e]]:=len[fan[e]]+t;

     flow:=flow+t;

     if dis[source]>=s then exit(flow);

     if aug=flow then break;

    end;

    val:=min(val,dis[v]);

   end;

   e:=next[e];

  end;

  if flow= then

  begin

   dec(gap[dis[u]]);

   if gap[dis[u]]= then dis[source]:=s;

   dis[u]:=val+;

   inc(gap[dis[u]]);

  end;

  exit(flow);

 end;

 function maxflow:longint;

 var ans:longint;

 begin

  fillchar(dis,sizeof(dis),);

  fillchar(gap,sizeof(gap),);

  gap[]:=s; ans:=;

  while dis[source]<s do ans:=ans+dfs(source,maxlongint);

  exit(ans);

 end;

 begin

  assign(input,'poj3498.in'); reset(input);

  assign(output,'poj3498.out'); rewrite(output);

  readln(cas);

  for v:= to cas do

  begin

   fillchar(head,sizeof(head),);

   tot:=; qq:=; s:=;

   read(n,d);

   for i:= to n do

   begin

    read(x[i],y[i],a[i],b[i]);

    qq:=qq+a[i];

   end;

   for i:= to n do

   begin

    inc(s); num[i,]:=s;

    inc(s); num[i,]:=s;

   end;

  inc(s); st:=s;

  for i:= to n do

   for j:= to n do

    if (i<>j)and(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))<=d) then

    begin

     fan[tot+]:=tot+;

     fan[tot+]:=tot+;

     add(num[i,],num[j,],maxlongint);

     add(num[j,],num[i,],);

    end;

  for i:= to n do

  begin

   fan[tot+]:=tot+;

   fan[tot+]:=tot+;

   add(num[i,],num[i,],b[i]);

   add(num[i,],num[i,],);

  end;

  for i:= to n do

  begin

   fan[tot+]:=tot+;

   fan[tot+]:=tot+;

   add(st,num[i,],a[i]);

   add(num[i,],st,);

  end;

  source:=st; ans:=;

  for i:= to tot do save[i]:=len[i];

  for i:= to n do

  begin

   src:=num[i,];

   if maxflow>=qq then

   begin

    inc(ans); c[ans]:=i;

   end;

   for j:= to tot do len[j]:=save[j];

  end;

  if ans= then writeln(-)

   else

   begin

    for i:= to ans- do write(c[i]-,' ');

    write(c[ans]-);

    writeln;

   end;

  end;

  close(input);

  close(output);

 end.

巴特西

【POJ3498】March of the Penguins（最大流，裂点）

最新文章

热门文章