【网络流24题】餐巾计划问题

发表于 | 分类于 | 阅读次数：

本篇题解将充分，全面地来解释建图的过程，以及其中的诸多细节。也欢迎各位指出其中不足。

拿到题后根据标签大体上可以判断出这是一个最小费用流。题目中有一段这样说道：

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。
但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

于是整理得，我们需要支持以下操作：

  • 将脏餐巾以f元/条送到快洗部，过m天后，干净餐巾送回来使用
  • 将脏餐巾以s元/条送到慢洗部，过n天后，干净餐巾送回来使用
  • 延期送洗（可能会出现之后餐巾需求过少，并不需要所有餐巾的情况）
  • 以p元/条购买新的餐巾

于是本题第一个难点就来了：如何处理脏餐巾和干净餐巾？

我们可以想到，每天开始的时候只有干净的餐巾可使用，每天结束的时候仅有脏的餐巾需要操作。于是将每天拆成两个点：起始点与结束点，分别处理不同时间段所需操作。

于是也可以想到：

  • 送到快洗部属于结束点操作，连向i+m天后的起始点，费用为f（表示餐巾洗好了，可使用）
  • 送到慢洗部属于结束点操作，连向i+n天后的起始点，费用为s
  • 延期送洗属于结束点操作，连向i+1的起始点，不需费用。
  • 购买新的餐巾属于起始点操作，目前并没有确定从哪连的，但费用为p。

以上操作流量均为$inf$

好了，到这里你有没有发现以上操作有什么共同点？

没错，他们都是连向起始点的有向边！

事实上，网络流24题的全称为“网络流与线性规划24题”，这也就告诉我们： 网络流的建图一定有顺序的，建的边一定是沿源点流向汇点，否则图就会不流通。

所以现在我们就弄明白了：我们应该将源点连接每天的结束点，而不是他们的起始点；起始点连向他们的汇点，容量为这天所需的餐巾数量，费用为0。

此外购买餐巾直接从源点购买即可。

之后跑一个裸的费用流即可。上我丑陋的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <cstring>
#include <queue>
#define N 2*n+1
#define inf 2147483647
using namespace std;

struct ed{
	int u,next,w,f;
}e[300000];
long long n,p,b,f,a,s,st=1,cost,ans;
int r[100000],d[100000],fir[100000],c[100000];
queue<int> q; bool v[100000];

bool spfa()
{
	for (int i=0;i<=N;i++) d[i]=inf/2,v[i]=0,c[i]=fir[i];
	q.push(0); v[0]=1; d[0]=0;
	while (!q.empty())
	{
		int k=q.front(); q.pop(); v[k]=0;
		for (int i=fir[k];i;i=e[i].next)
		{
			int u=e[i].u,w=e[i].f;
			if (d[u]>d[k]+w&&e[i].w)
			{
				d[u]=d[k]+w; if (!v[u]) v[u]=1,q.push(u); 
			} 
		}
	}
	return (d[N]<inf/2);
}

int dfs(int p,int now)
{
	if (p==N) {
		v[N]=1; ans+=now; return now;
	}
	int mw=0,used=0;  v[p]=1;
	for (int i=c[p];i;i=e[i].next){
		c[p]=1; int u=e[i].u,w=e[i].f;
		if ((!v[u]||u==N)&&d[u]==d[p]+w&&e[i].w)
		if (mw=dfs(u,min(now-used,e[i].w)))
		{
			e[i].w-=mw; e[i^1].w+=mw; used+=mw;
			cost+=w*mw; if (used==now) break;
		}
	}
	return used;
}

long long dinic()
{
	while (spfa())
	{
		v[N]=1;
		while (v[N])
		{
			memset(v,0,sizeof(v));
			dfs(0,inf);
		}
		
	}
	return cost;
}

void add(int x,int y,int w,int f)
{
	e[++st].u=y; e[st].next=fir[x]; e[fir[x]=st].w=w; e[st].f=f;
	e[++st].u=x; e[st].next=fir[y]; e[fir[y]=st].w=0; e[st].f=-f;
	
}

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>r[i];
		add(0,i,r[i],0); add(i+n,N,r[i],0);
        //源点连接结束点，起始点连向他们的汇点。
	}
	cin>>p>>a>>f>>b>>s;
	for (int i=1;i<=n;i++)
	{
		add(0,i+n,inf,p);  //从源点购买餐巾
		if (i+1<=n) add(i,i+1,inf,0);   //把今天的脏毛巾拖到明天 
		if (i+a<=n) add(i,i+n+a,inf,f); //把餐巾送到快洗部
		if (i+b<=n) add(i,i+n+b,inf,s); //把餐巾送到慢洗部
	}
    //可以注意到，以上的连边均是由源点向汇点的。
	cout<<dinic()<<endl;
}