【洛谷P1251】餐巾计划问题

题目

题目链接：https://www.luogu.com.cn/problem/P1251
一个餐厅在相继的 (N) 天里,每天需用的餐巾数不尽相同。假设第 (i) 天需要 (r_i)块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 (p) 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 (n) 天((n<m)),其费用为 (s) 分((s<f))。
每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。
试设计一个算法为餐厅合理地安排好 (N) 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
(Nleq 200,rileq 10000000,p,f,sleq 10000)。

思路

考虑费用流，那么显然把每一天看做点，这样的话，每一天都要向汇点连流量为 (r_i) 的边，但是这样的话我们就不好处理用脏的餐巾可以送去洗的设定了，所以肯定是拆点的。
我们把每一个点拆成两个点 (x_1,x_2)，因为每一天一定都是恰好产生 (r_i) 条脏毛巾，所以可以直接从 (S) 向 (x_1) 连一条 ((r_x,0)) 的边，表示每天产生 (r_x) 条脏毛巾；(x_2) 向 (T) 连一条 ((r_x,0)) 的边，表示每一条用掉 (r_x) 条毛巾。
这样的好处是我们成功把干净毛巾和脏毛巾分离了，他们之间的流量互不影响。不用考虑脏毛巾拿去洗的问题。
接下来脏毛巾可以留着过夜，(x_1 o (x+1)_1)，((+infty,0))；可以拿去洗，(x_1 o (x+t_1)_2)，((+infty,c_1))；(x_1 o (x+t_2)_2)，((+infty,c_2))。
然后跑最小费用最大流即可。

代码

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

const int N=4010,M=2000010,Inf=1e9;
int n,t,c,S,T,tot=1,a[N],head[N],pre[N];
bool vis[N];
ll dep[N],cost;

struct edge
{
	int next,to,flow,cost;
}e[M];

void add(int from,int to,int flow,int cost)
{
	e[++tot]=(edge){head[from],to,flow,cost};
	head[from]=tot;
	swap(from,to);
	e[++tot]=(edge){head[from],to,0,-cost};
	head[from]=tot;
}

bool spfa()
{
	memset(dep,0x3f3f3f3f,sizeof(dep));
	queue<int> q;
	q.push(S); dep[S]=0;
	while (q.size())
	{
		int u=q.front(); q.pop();
		vis[u]=0;
		for (int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].to;
			if (e[i].flow && dep[v]>dep[u]+e[i].cost)
			{
				dep[v]=dep[u]+e[i].cost; pre[v]=i;
				if (!vis[v]) { q.push(v); vis[v]=1; }
			}
		}
	}
	return dep[T]<Inf;
}

void addflow()
{
	int minf=Inf;
	for (int i=T;i!=S;i=e[pre[i]^1].to)
		minf=min(minf,e[pre[i]].flow);
	for (int i=T;i!=S;i=e[pre[i]^1].to)
	{
		e[pre[i]].flow-=minf;
		e[pre[i]^1].flow+=minf;
	}
	cost+=1LL*minf*dep[T];
}

void MCMF()
{
	while (spfa()) addflow();
}

int main()
{
	memset(head,-1,sizeof(head));
	S=N-1; T=N-2;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&c);
	for (int i=1;i<=n;i++)
	{
		add(S,i,a[i],0); add(i+n,T,a[i],0);
		add(S,i+n,Inf,c);
		if (i<n) add(i,i+1,Inf,0);
	}
	scanf("%d%d",&t,&c);
	for (int i=1;i+t<=n;i++)
		add(i,i+n+t,Inf,c);
	scanf("%d%d",&t,&c);
	for (int i=1;i+t<=n;i++)
		add(i,i+n+t,Inf,c);
	MCMF();
	printf("%lld",cost);
	return 0;
}