本文共 2381 字，大约阅读时间需要 7 分钟。

题目大意

原题链接：

一个餐厅运营n天，每天分别需要n₁，n₂…张干净的餐巾，每天能获得餐巾的方式有三种，一是新买，一张p元；二是之前买的用完后送到快洗店，需要洗k天，一张ff元；三是用完后送到慢洗店，需要洗m天，一张ss元。新毛巾和洗好的毛巾不能储存，但是脏毛巾可以储存在餐厅，费用为0。现在问假设最开始时没有餐巾，要满足这n天的餐巾需求，n天总共要花多少钱？

思路

把餐巾想象成一个流，就会发现可以用网络流来解决这个问题。将每一种餐巾使用方案转化成一个可行流的方案，将费用加到相应的来源的边上，就成了一个求最小费用最大流的问题了。然后每天的这个点是有限制的，每天都必须要n_i的餐巾，所以就要拆点，来完成对点的限制，把每天拆成早上和晚上两个点，通过建边来巧妙的实现这两个点和边的限制，来达到题目的意思。所有建边如下：

1. 每天早上可以购买无限多的餐巾；从源点s向每天早上的点连一条容量为正无穷，费用为p的边
2. 每天晚上可以获得n_i条脏餐巾；从源点向每天晚上的点连一条容量为n_i，费用为0得边
3. 每天早上都需要收到n_i条餐巾；从每天早上的点向汇点t连一条容量为n_i，费用为0的边
4. 每天晚上的脏餐巾可以给到k天后的早上；从晚上的点向k天后的早上连一条容量为正无穷，费用为ff的边
5. 每天晚上的脏餐巾还可以给到m天后的早上；从晚上的点向m天后的早上连一条容量为正无穷，费用为ss的边
6. 每天晚上的脏餐巾也可以给到下一天的晚上，储存起来；从晚上的点向下一天的晚上连一条容量为正无穷，费用为0的边

图论最重要的就是建图，如上建好图后，我们只需要跑一下最小费用最大流即可求出最小费用。

有几个常见的错误想法：我们将晚上产生的脏毛巾通过清洗，向后面所有满足条件的每一天连边。这样最坏情况下复杂度是n²，会TLE，所以直接从今晚向明晚连边，代表脏毛巾存到了第二天再送去洗，就很巧妙地解决了，跑的飞快。

代码详解

#include
   
    #include
    
     #include
     
      using namespace std;const int N = 1610,M = 10010,INF = 0x3f3f3f3f;int n,s,t,p,k,m,ff,ss,flow;int e[M],ne[M],w[M],f[M],h[N],idx;int pre[N],dis[N];bool vis[N];void add(int a,int b,int c,int d){
   	e[idx] = b;	w[idx] = d;	f[idx] = c;	ne[idx] = h[a];	h[a] = idx++;	e[idx] = a;	w[idx] = -d;	f[idx] = 0;	ne[idx] = h[b];	h[b] = idx++;}bool spfa(){
   	queue
      
        q;	memset(dis,INF,sizeof dis);	memset(vis,0,sizeof vis);	memset(pre,-1,sizeof pre);	q.push(s);	dis[s] = 0;	while(q.size())	{
   		int u = q.front();		q.pop();		vis[u] = 0;		for(int i = h[u];~i;i = ne[i])		{
   			int v = e[i];			if(dis[v] > dis[u]+w[i] && f[i])			{
   				dis[v] = dis[u] + w[i];				pre[v] = i;				if(!vis[v])				{
   					vis[v] = 1;					q.push(v);				}			}		}	}	if(pre[t] != -1)		return 1;	else		return 0;}int EK(){
   	int cost = 0;	while(spfa())	{
   		int minf = INF;		for(int i = pre[t];~i;i = pre[e[i^1]])			minf = min(minf,f[i]);		for(int i = pre[t];~i;i = pre[e[i^1]])		{
   			f[i] -= minf;			f[i^1] += minf;			cost += minf * w[i];		}	}	return cost;}int main(){
   	cin >> n >> p >> k >> ff >> m >> ss;	s = 0,t = 1;	memset(h,-1,sizeof h);	for(int i = 1;i <= n;i++)	{
   		int a;		cin >> a;	//将第i天早上的点序号记为i*2，晚上记为i*2+1		add(s,i*2+1,a,0);	//建边的种类：2		add(s,i*2,INF,p);	//1		add(i*2,t,a,0);		//3		if(i+k <= n)			add(i*2+1,(i+k)*2,INF,ff);	//4		if(i+m <= n)			add(i*2+1,(i+m)*2,INF,ss);	//5		if(i != n)			add(i*2+1,(i+1)*2+1,INF,0);	//6	}	cout << EK() << endl;	//最小费用最大流	return 0;}
      
     
    
   

转载地址：http://ybbki.baihongyu.com/