[网络流24题]洛谷P1251 / Acwing 2184：餐巾计划问题（建图+拆点+最小费用最大流）

女爷i 2022-11-05 03:29 147阅读 0赞

### 题目大意 ###

原题链接：  
[Acwing 2184： 餐巾计划问题][Acwing 2184_]  
[洛谷P1251： 餐巾计划问题][P1251_]

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

### 思路 ###

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

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

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

有几个常见的错误想法：我们将晚上产生的脏毛巾通过清洗，向后面所有满足条件的每一天连边。这样最坏情况下复杂度是n2，会TLE，所以直接从今晚向明晚连边，代表脏毛巾存到了第二天再送去洗，就很巧妙地解决了，跑的飞快。  
而且晚上的点是和源点相连的，可以理解为会产生这么多脏毛巾，而不是和早上相连的，如果和早上相连跑出来的就不算最小费用了，费用会大。

### 代码详解 ###

#include<iostream>
    #include<cstring>
    #include<queue>
    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<int> 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;
    }

[Acwing 2184_]: https://www.acwing.com/problem/content/2186/
[P1251_]: https://www.luogu.com.cn/problem/P1251