自动搬运

查看原文

来自洛谷，原作者为

	TEoS 水平不够运气来凑

搬运于2025-08-24 21:35:20，当前版本为作者最后更新于2019-09-02 10:50:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本文会具体地对建模进行讲解和分析。

算法

最小费用最大流

建模

因为每天使用的毛巾是固定的，我们不需要去关心这个部分。显然，我们的任务就是处理每天晚上使用过的毛巾和给每天早上提供毛巾。而网络的流就相当于毛巾从源点产生，经过网络之后给汇点提供新毛巾。源点产生的毛巾可以是旧的或新的，接下来会详细讲解。

很容易想到拆点的思想，将每天拆成早上和晚上，分别进行处理。本文中设第$i$天的早上和晚上的节点编号分别为$i$和$i+n$。

1. 每天晚上从源点获得当天使用过的旧毛巾，不需要费用，第$i$天的数量为$n_i$，即从源点$s$向$i+n(i\in[1,n])$连一条流量为$n_i$，费用为$0$的边。
2. 每天早上向汇点提供当天需要的新毛巾，不需要费用，第$i$天的数量为$n_i$，即从$i(i\in[1,n])$向汇点$t$连一条流量为$n_i$，费用为$0$的边。
3. 每天早上可以从汇点购买毛巾，单位费用为$f$，数量不限，即从源点$s$向$i(i\in[1,n])$连一条流量为$inf$，费用为$f$的边。
4. 每天晚上可以把旧毛巾送去以$A$方式进行消毒，单位费用为$f_a$，数量不限，需要到$a$天后的早上才可以使用。注意，这里的$a$天是指全天，即若第$1$天晚上送毛巾去消毒，消毒需要$1$天，要到第$3$天早上才可以用。同时要注意边界问题，不能超出$n$天的范围。即从$i+n(i\in[1,n-a-1])$向$i+a+1$连一条流量为$inf$，费用为$f_a$的边。
5. 同理，每天晚上还可以把旧毛巾送去以$B$方式进行消毒，单位费用是$f_b$，数量不限，即从$i+n(i\in[1,n-b-1])$向$i+b+1$连一条流量为$inf$，费用为$f_b$的边。
6. 每一天晚上还可以选择不处理部分毛巾，把毛巾留到第二天晚上，不需要费用。这里有几点要说明，第一，因为旧毛巾不能使用，所以要留到第二天晚上而不是早上；第二，虽然根据贪心的思想是越早消毒越好，但实际上有可能消毒了却不需要用的情况出现，因此可以将旧毛巾留到第二天晚上。实际上也可以从每一条早上向第二天早上连边，表示将新毛巾留到第二天早上使用，也是同样的道理，都可行。这个操作也要注意边界问题。即从$i+n(i\in[1,n-1])$向$i+1+n$连一条流量为$inf$，费用为$0$的边。

以上就是全部的建模，建模之后求最小费用最大流即可。

最后给出代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ano ((i-1)^1)+1
using namespace std;
const int INF=0x7f7f7f7f,N=2e3+100,M=6e3+100;
int n,a,b,f,fa,fb,tot,ans,s,t;
int head[N],ver[2*M],edge[2*M],Next[2*M],cost[2*M];
int pre[N],minf[N],d[N];
bool v[N];
void add(int x,int y,int z,int c)
{
	ver[++tot]=y,edge[tot]=z,cost[tot]=c,Next[tot]=head[x],head[x]=tot;
	ver[++tot]=x,edge[tot]=0,cost[tot]=-c,Next[tot]=head[y],head[y]=tot;
}//网络流双向建边
bool spfa()
{
	memset(v,0,sizeof(v));
	memset(d,0x7f,sizeof(d));
	queue<int> q;
	d[s]=0,v[s]=1,minf[s]=INF;
	q.push(s);
	while(q.size())
	{
		int x=q.front();q.pop();v[x]=0;
		for(int i=head[x];i;i=Next[i])
			if(edge[i])
			{
				int y=ver[i];
				if(d[x]+cost[i]<d[y])
				{
					d[y]=d[x]+cost[i];
					minf[y]=min(minf[x],edge[i]);
					pre[y]=i;
					if(!v[y])
					{
						q.push(y);
						v[y]=1;
					}
				}
			}
	}
	return d[t]!=INF;
}
void update()
{
	int x=t;
	while(x!=s)
	{
		int i=pre[x];
		edge[i]-=minf[t];
		edge[ano]+=minf[t];
		x=ver[ano];
	}
	ans+=d[t]*minf[t];
}//最小费用最大流模板
int main()
{
	scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
	t=2*n+1,a++,b++;//也可以先将a,b分别加1，后面就不用加1
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		add(s,i+n,x,0),add(i,t,x,0),add(s,i,INF,f);//1,2,3操作
		if(i+a<=n)
			add(i+n,i+a,INF,fa);//4操作
		if(i+b<=n)
			add(i+n,i+b,INF,fb);//5操作
		if(i+1<=n)
			add(i,i+1,INF,0);//6操作，这里是从每天早上向第二天早上连边
	}
	while(spfa())
		update();//跑最小费用最大流。
	printf("%d",ans);
	return 0;
}