首页 > 代码库 > 【Codevs1237&网络流24题餐巾计划】(费用流)

【Codevs1237&网络流24题餐巾计划】(费用流)

题意:一个餐厅在相继的 N 天里,每天需用的餐巾数不尽相同。

假设第 i 天需要 ri块餐巾(i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 p 分;

或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;

或者送到慢洗部,洗一块需 n 天(n>m),其费用为 s<f 分。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。

但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划,使总的花费最小。 
编程找出一个最佳餐巾使用计划。

思路:RYZ作业

费用流经典模型之一

 

BYVOID:

【建模方法】
把每天分为二分图两个集合中的顶点Xi,Yi,建立附加源S汇T。
1、从S向每个Xi连一条容量为ri,费用为0的有向边。
2、从每个Yi向T连一条容量为ri,费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大,费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大,费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大,费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大,费用为s的有向边。
求网络最小费用最大流,费用流值就是要求的最小总花费。
【建模分析】
这个问题的主要约束条件是每天的餐巾够用,而餐巾的来源可能是最新购买,也可能是前几天送洗,

今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部,或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理,建模后就是二分图。

二分图X集合中顶点Xi表示第i天用完的餐巾,其数量为ri,所以从S向Xi连接容量为ri的边作为限制

Y集合中每个点Yi则是第i天需要的餐巾,数量为ri,与T连接的边容量作为限制。

每天用完的餐巾可以选择留到下一天(Xi->Xi+1),不需要花费,

送到快洗部(Xi->Yi+m),费用为f,

送到慢洗部(Xi->Yi+n),费用为s。

每天需要的餐巾除了刚刚洗好的餐巾,还可能是新购买的(S->Yi),费用为p。

在网络上求出的最小费用最大流,满足了问题的约束条件(因为在这个图上最大流一定可以使与T连接的边全部满流,其他边只要有可行流就满足条件),

而且还可以保证总费用最小,就是我们的优化目标。

 

  1 var head,vet,next,len1,len2,fan:array[1..2100000]of longint;
  2     inq:array[1..5000]of boolean;
  3     q:array[0..5000]of longint;
  4     num,pre:array[1..5000,1..2]of longint;
  5     dis,a:array[1..5000]of longint;
  6     n,m,p1,m1,f1,n1,s1,ans,source,src,s,tot,i,j:longint;
  7 
  8 function min(x,y:longint):longint;
  9 begin
 10  if x<y then exit(x);
 11  exit(y);
 12 end;
 13 
 14 procedure add(a,b,c,d:longint);
 15 begin
 16  inc(tot);
 17  next[tot]:=head[a];
 18  vet[tot]:=b;
 19  len1[tot]:=c;
 20  len2[tot]:=d;
 21  head[a]:=tot;
 22 
 23  inc(tot);
 24  next[tot]:=head[b];
 25  vet[tot]:=a;
 26  len1[tot]:=0;
 27  len2[tot]:=-d;
 28  head[b]:=tot;
 29 end;
 30 
 31 function spfa:boolean;
 32 var u,e,v,i,t,w:longint;
 33 begin
 34  for i:=1 to s do
 35  begin
 36   dis[i]:=maxlongint>>1;
 37   inq[i]:=false;
 38  end;
 39  t:=0; w:=1; q[1]:=source; dis[source]:=0; inq[source]:=true;
 40  while t<w do
 41  begin
 42   inc(t); u:=q[t mod 5000]; inq[u]:=false;
 43   e:=head[u];
 44   while e<>0 do
 45   begin
 46    v:=vet[e];
 47    if (len1[e]>0)and(dis[u]+len2[e]<dis[v]) then
 48    begin
 49     dis[v]:=dis[u]+len2[e];
 50     pre[v,1]:=u;
 51     pre[v,2]:=e;
 52     if not inq[v] then
 53     begin
 54      inc(w); q[w mod 5000]:=v; inq[v]:=true;
 55     end;
 56    end;
 57    e:=next[e];
 58   end;
 59  end;
 60  if dis[src]=maxlongint>>1 then exit(false);
 61  exit(true);
 62 end;
 63 
 64 procedure mcf;
 65 var k,e,t:longint;
 66 begin
 67  k:=src; t:=maxlongint;
 68  while k<>source do
 69  begin
 70   t:=min(t,len1[pre[k,2]]);
 71   k:=pre[k,1];
 72  end;
 73  k:=src;
 74  while k<>source do
 75  begin
 76   e:=pre[k,2];
 77   len1[e]:=len1[e]-t;
 78   len1[fan[e]]:=len1[fan[e]]+t;
 79   ans:=ans+t*len2[e];
 80   k:=pre[k,1];
 81  end;
 82 end;
 83 
 84 begin
 85  assign(input,codevs1237.in); reset(input);
 86  assign(output,codevs1237.out); rewrite(output);
 87  readln(n,p1,m1,f1,n1,s1);
 88  for i:=1 to 2100000 do
 89   if i and 1=1 then fan[i]:=i+1
 90    else fan[i]:=i-1;
 91  for i:=1 to n do read(a[i]);
 92  for i:=1 to n do
 93   for j:=1 to 2 do
 94   begin
 95    inc(s); num[i,j]:=s;
 96   end;
 97  source:=s+1; src:=s+2; s:=s+2;
 98  for i:=1 to n do add(source,num[i,1],a[i],0);
 99  for i:=1 to n do add(num[i,2],src,a[i],0);
100  for i:=1 to n-1 do add(num[i,1],num[i+1,1],maxlongint,0);
101  for i:=1 to n do add(source,num[i,2],maxlongint,p1);
102  for i:=1 to n do
103   if i+m1<=n then add(num[i,1],num[i+m1,2],maxlongint,f1);
104  for i:=1 to n do
105   if i+n1<=n then add(num[i,1],num[i+n1,2],maxlongint,s1);
106  while spfa do mcf;
107  writeln(ans);
108  close(input);
109  close(output);
110 end.

 

【Codevs1237&网络流24题餐巾计划】(费用流)