【线性规划与网络流24题 10】餐巾计划

Description

一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。

编程任务：编程找出一个最佳餐巾使用计划.

Input

第1 行有6 个正整数N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n是慢洗部洗一块餐巾需用天数；s是慢洗部洗一块餐巾需要的费用。
接下来的N 行是餐厅在相继的N 天里，每天需用的餐巾数。

Output

程序运行结束时，将餐厅在相继的N 天里使用餐巾的最小总花费输出

Sample Input

3 10 2 3 3 2
5
6
7

Sample Output

145

Hint

题目中所有数字都不超过1000

看完题目很明显知道是一个最小费用最大流！

但是怎么建图呢？

二分图的思想来搞：X集合代表每个节点用过的餐巾，Y集合代表每个节点需要的餐巾（也就是拆点）

S-X：代表每个点用了多少：从S向每个Xi连一条容量为ri，费用为0的有向边

Y-T：代码每个点需要用多少：从每个Yi向T连一条容量为ri，费用为0的有向边

然后就是Y中需要使用的餐巾怎么来：

题目中的描述是有3种途径的

第一种：直接购买，那么是从S过来：从S向每个Yi连一条容量为无穷大，费用为p的有向边

第二种：慢洗：从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边

第三种：快洗：从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边

当然，可以不洗，留到之后再处理

从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边

建图建好了，之后，跑个模板就好了

#include<bits/stdc++.h>
using namespace std;

const int maxn=10000;
const int maxm=300000;
const int inf=0x3f3f3f3f;

struct Edge{
	int to,nxt,cap,flow,cost;
}edge[maxm];

int Head[maxn],tol,pre[maxn],dis[maxn];
bool vis[maxn];

int n,m,s,t,tot;
void init(){
	tol=0;
	memset(Head,-1,sizeof(Head));
}

void addedge(int u,int v,int cap,int cost){
	edge[tol].to=v;
	edge[tol].cap=cap;
	edge[tol].cost=cost;
	edge[tol].flow=0;
	edge[tol].nxt=Head[u];
	Head[u]=tol++;
	edge[tol].to=u;
	edge[tol].cap=0;
	edge[tol].cost=-cost;
	edge[tol].flow=0;
	edge[tol].nxt=Head[v];
	Head[v]=tol++;
}

bool spfa(int s,int t){
	queue<int> q;
	for(int i=0;i<tot;i++){
		dis[i]=inf;
		vis[i]=false;
		pre[i]=-1;
	}
	dis[s]=0;
	vis[s]=true;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=Head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){
				dis[v]=dis[u]+edge[i].cost;
				pre[v]=i;
				if (!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	if (pre[t]==-1) return false;
	return true;
}

int minCostMaxflow(int s,int t,int &cost){
	int flow=0;
	cost=0;
	while(spfa(s,t)){
		int Min=inf;
		for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
			if (Min>edge[i].cap-edge[i].flow)
				Min=edge[i].cap-edge[i].flow;
		for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
			edge[i].flow+=Min;
			edge[i^1].flow-=Min;
			cost+=edge[i].cost*Min;
		}
		flow+=Min;
	}
	return flow;
}

int main(){
	//freopen("input.txt","r",stdin);
	int N,pp,mm,ff,nn,ss,x;
	scanf("%d%d%d%d%d%d",&N,&pp,&mm,&ff,&nn,&ss);
	init();
	n=N;
	s=0;t=2*n+1;tot=2*n+2;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		addedge(s,i,x,0);
		addedge(i+n,t,x,0);
		addedge(s,i+n,inf,pp);
		if (i<n) addedge(i,i+1,inf,0);
		if (i+mm<=n) addedge(i,i+mm+n,inf,ff);
		if (i+nn<=n) addedge(i,i+nn+n,inf,ss);
	}
	minCostMaxflow(s,t,x);
	printf("%d\n",x);
	return 0;
}