【Codevs1034】家园（最大流，裂点）

题意：由于人类对自然的疯狂破坏，人们意识到在大约2300年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。
现有n个太空站处于地球与月球之间（编号1..n），m艘公共交通太空船在其中来回穿梭，每个太空站Si可容纳无限的人，每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi，将周期性地停靠一系列的太空站（Si1,Si2…Sir），如：（1，3，4）表示停靠太空站1 3 4 1 3 4 1 3 4 …。任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为1。人只能在太空船停靠太空站（或地球、月球）时上船或下船。初始时的人全在地球上，太空船全在初始站（太空船pi处于Si1），目标是让所有的人尽快地全部转移到月球上。

文件第一行为三个正整数 n（太空站个数）、 m（太空船个数）、 k（需要运送的地球上的人的个数），其中 1<=m<=13, 1<=n<=20, 1<=k<=50。

思路：按时间裂点跑最大流

num[i,j]表示i秒后的j点

(i,j)-->(i+1,j)连流量为无限边

(i,x)-->(i+1,y)连流量为h[k]的边，x,y为k号飞船分别在i,i+1时刻停留的星球

枚举答案并加边，dinic即可

注意每次最大流跑完后要把流量还原重构，改了很长时间没改出来

自己还是Too Simple

顺便说一句1999年的官方数据第二组是错的，正确答案是5，OUT是7

 var head,vet,next,len,dis,gap,fan,h,r,save:array[..]of longint;

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

     n,m,i,j,k,x,ans,tot,source,src,s:longint;

 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,val,flow,t:longint;

 begin

  if u=src then exit(aug);

  flow:=;

  e:=head[u]; 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,'codevs1034.in'); reset(input);

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

  readln(n,m,k);

  for i:= to  do

   for j:= to n+ do

   begin

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

   end;

  for i:= to m do

  begin

   read(h[i]); read(r[i]);

   for j:= to r[i] do

   begin

    read(a[i,j]);

    if a[i,j]= then a[i,j]:=n+;

    if a[i,j]=- then a[i,j]:=n+;

   end;

   x:=; b[i,]:=a[i,];

   for j:= to  do

   begin

    inc(x); if x=r[i]+ then x:=;

    b[i,j]:=a[i,x];

   end;

  end;

  ans:=-;

  source:=num[,n+];

  for i:= to  do

  begin

   for j:= to tot do save[j]:=len[j]; //重构边的容量，极其重要

   src:=num[i,n+]; s:=src;

   if maxflow>=k then begin ans:=i; break; end;

   for j:= to tot do len[j]:=save[j]; //重构边的容量，极其重要

   for j:= to m do

   begin

    fan[tot+]:=tot+;

    fan[tot+]:=tot+;

    add(num[i,b[j,i]],num[i+,b[j,i+]],h[j]);

  //  writeln(i,' ',b[j,i],' ',i+,' ',b[j,i+],' ',h[j]);

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

   // writeln(i+,' ',b[j,i+],' ',i,' ',b[j,i],' ',);

   end;

   for j:= to n+ do

   begin

    fan[tot+]:=tot+;

    fan[tot+]:=tot+;

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

   // writeln(i,' ',j,' ',i+,' ',j,' ',maxlongint);

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

   // writeln(i+,' ',j,' ',i,' ',j,' ',);

   end;

   writeln;

  end;

  if ans> then writeln(ans)

   else writeln();

  //close(input);

  //close(output);

 end.

巴特西

【Codevs1034】家园（最大流，裂点）

最新文章

热门文章