【Codevs1993】草地排水（最大流，Dinic）

题意：在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

(0 <= N <= 200) 和 M (2 <= M <= 200)

Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

思路：最大流，Dinic模板。

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

     n,m,i,x,y,z,tot,src,source: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,t,val,flow:longint;

 begin

  if u=src then exit(aug);

  flow:=; val:=n-;

  e:=head[u];

  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]>=n 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]:=n;

   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[]:=n; ans:=;

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

  exit(ans);

 end;

 begin

  readln(m,n);

  for i:= to m do

  begin

   readln(x,y,z);

   fan[tot+]:=tot+;

   fan[tot+]:=tot+;

   add(x,y,z);

   add(y,x,);

  end;

  source:=; src:=n;

  writeln(maxflow);

 end.

巴特西

【Codevs1993】草地排水（最大流，Dinic）

最新文章

热门文章