「网络流24题」餐巾计划问题
题目描述 Description
一个餐厅在相继的 N 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为 p 分；或者把旧餐巾送到快洗部，洗一块需 m 天，其费用为 f 分；或者送到慢洗部，洗一块需 n 天(n>m)，其费用为 s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 N 天中餐巾使用计划，使总的花费最小。
编程找出一个最佳餐巾使用计划.
输入描述 Input Description
第 1 行有 6 个正整数 N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n 是慢洗部洗一块餐巾需用天数；s 是慢洗部洗一块餐巾需要的费用。接下来的 N 行是餐厅在相继的 N 天里，每天需用的餐巾数。
输出描述 Output Description
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
样例输入 Sample Input
3 10 2 3 3 2
5
6
7
样例输出 Sample Output
145
题解：参考了hzwer的代码
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图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。
#include<iostream>
#include<cstdio>
#define inf 0x7fffffff
#define T 2001
using namespace std;
int cnt=1,day,p,m,f,n,s,ans;
int from[2005],q[2005],dis[2005],head[2005];
bool inq[2005];
struct data{int from,to,next,v,c;}e[1000001];//v 流，c 费用
void ins(int u,int v,int w,int c)
{
cnt++;
e[cnt].from=u;e[cnt].to=v;
e[cnt].v=w;e[cnt].c=c;
e[cnt].next=head[u];head[u]=cnt;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa()
{
for(int i=0;i<=T;i++)dis[i]=inf;
int t=0,w=1,i,now;
dis[0]=q[0]=0;inq[0]=1;
while(t!=w)//队列，宽搜
{
now=q[t];t++;if(t==2001)t=0;
for(int i=head[now];i;i=e[i].next)
{
if(e[i].v&&dis[e[i].to]>dis[now]+e[i].c)
{
from[e[i].to]=i;
dis[e[i].to]=dis[now]+e[i].c;
if(!inq[e[i].to])
{
inq[e[i].to]=1;
q[w++]=e[i].to;
if(w==2001)w=0;
}
}
}
inq[now]=0;
}
if(dis[T]==inf)return 0;return 1;
}
void mcf()
{
//x记录这条最短路（源点到汇点的最小费用，求最短路过程中，点之间的边权用费用代替）上的最小容量
int i,x=inf;
i=from[T];
while(i)
{
x=min(e[i].v,x);
i=from[e[i].from];
}
//x为这条增光路上的最小容量
//根据记录的前驱，从汇点沿着前驱返回源点，对经过的边减去这个最短路径流过的流量，反向边加上相应的流量
i=from[T];
while(i)
{
e[i].v-=x;
e[i^1].v+=x;
ans+=x*e[i].c;
i=from[e[i].from];
}
}
int main()
{
scanf("%d%d%d%d%d%d",&day,&p,&m,&f,&n,&s);
for(int i=1;i<=day;i++)
{
if(i+1<=day)insert(i,i+1,inf,0);//起点，终点，容量，费用
if(i+m<=day)insert(i,day+i+m,inf,f);
if(i+n<=day)insert(i,day+i+n,inf,s);
insert(0,day+i,inf,p);
}
int x;
for(int i=1;i<=day;i++)
{
scanf("%d",&x);
insert(0,i,x,0);
insert(day+i,T,x,0);
}
while(spfa())mcf();
printf("%d",ans);
return 0;
}