Libre 6008 「网络流 24 题」餐巾计划 （网络流，最小费用最大流）

Description

一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。

(1)购买新的餐巾，每块需p分；

(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f＜p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。

(3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s＜f)。

在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。

Input

共 n+1 行：

第1行为总天教和每块餐巾的新购费用p,快洗所需天数d1，快洗所需费用c1，慢洗所需天数d2，慢洗所需费用c2；

下n行为每天所需的餐巾块数；

Output

一行，最小的费用

Sample Input

3 10 2 3 3 2

5

6

7

Sample Output

145

Http

Libre:https://loj.ac/problem/6008

Source

网络流，最小费用最大流

解决思路

题目还算好理解，但是建图需要考虑一些东西。

餐巾不管在那一天洗价格都是一样的，所以没有必要提前把旧餐巾洗成新餐巾让后放在那里不用。

首先对于每一天i，我们将其拆成两个点i和i+n，我们把前面一个称为旧餐巾，后面一个称为新餐巾。另建立源点0和汇点n*2+1。

需要连接的边有：

1 源点到旧餐巾，容量为r[i]（就是第i天的餐巾需求啦），代价为0，这条表表示这一天有r[i]条新的旧餐巾产生

2 源点到新餐巾，容量为无穷大，代价为新购餐巾的费用。这条边的意思就是新购餐巾

3 新餐巾到汇点，容量为R[i]，代价为0。这条边使用来限制第i天只能花掉r[i]条餐巾，也代表着强制让剩余的餐巾向后流，即不让多余的餐巾提前洗掉

4 从第i天的旧餐巾到第i+1天的旧餐巾，容量为无穷大，代价为0。这条边代表的是延时送洗，即把餐巾送到后面几天去

5 从第i天的旧餐巾到第i+d1（即快洗所需时间）天的新餐巾，容量为无穷大，代价为快洗所需代价。这条边代表送到快洗部快洗

6 从第i天的旧餐巾到第i+d2（即慢洗所需时间）天的新餐巾，容量为无穷大，代价为慢洗所需代价。这条边代表送到慢洗部慢洗

然后跑一边spfa最小费用最大流即可。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxN=3100;

const int maxM=maxN*maxN*2;

const int inf=2147483647;

class Edge

{

public:

	int u,v,cost,flow;

};

int n,P,d1,c1,d2,c2;

int cnt=-1;

int Head[maxN];

int Next[maxM];

Edge E[maxM];

int Dist[maxN];

int path[maxN];

int Q[maxN*100];

bool inqueue[maxN];

int Flow[maxN];

void Add_Edge(int u,int v,int cost,int flow);

bool spfa();

int main()

{

	memset(Head,-1,sizeof(Head));

	scanf("%d%d%d%d%d%d",&n,&P,&d1,&c1,&d2,&c2);

	for (int i=1;i<=n;i++)

	{

		int r;

		scanf("%d",&r);

		Add_Edge(0,i,0,r);//源点到旧餐巾

		Add_Edge(0,i+n,P,inf);//从源点到新餐巾，即新购买餐巾

		Add_Edge(i+n,n*2+1,0,r);//从新餐巾到汇点，表示要用掉这么多餐巾

		if (i+1<=n)

			Add_Edge(i,i+1,0,inf);//延时送洗

		if (i+d1<=n)

			Add_Edge(i,i+d1+n,c1,inf);//送到快洗部

		if (i+d2<=n)

			Add_Edge(i,i+d2+n,c2,inf);//送到慢洗部

	}

	int Ans=0;

	while (spfa())

	{

		int now=n*2+1;

		int p=path[now];

		while (now!=0)

		{

			E[p].flow-=Flow[n*2+1];

			E[p^1].flow+=Flow[n*2+1];

			now=E[p].u;

			p=path[now];

		}

		Ans+=Flow[n*2+1]*Dist[n*2+1];

	}

	cout<<Ans<<endl;

	return 0;

}

void Add_Edge(int u,int v,int cost,int flow)

{

	cnt++;

	Next[cnt]=Head[u];

	Head[u]=cnt;

	E[cnt].u=u;

	E[cnt].v=v;

	E[cnt].cost=cost;

	E[cnt].flow=flow;

	cnt++;

	Next[cnt]=Head[v];

	Head[v]=cnt;

	E[cnt].u=v;

	E[cnt].v=u;

	E[cnt].cost=-cost;

	E[cnt].flow=0;

}

bool spfa()

{

	memset(Dist,-1,sizeof(Dist));

	memset(inqueue,0,sizeof(inqueue));

	int h=1,t=0;

	Q[1]=0;

	Dist[0]=0;

	inqueue[0]=1;

	Flow[0]=inf;

	do

	{

		t++;

		int u=Q[t];

		inqueue[u]=0;

		for (int i=Head[u];i!=-1;i=Next[i])

		{

			int v=E[i].v;

			if ((E[i].flow>0)&&((E[i].cost+Dist[u]<Dist[v])||(Dist[v]==-1)))

			{

				Dist[v]=Dist[u]+E[i].cost;

				path[v]=i;

				Flow[v]=min(Flow[u],E[i].flow);

				if (inqueue[v]==0)

				{

					h++;

					Q[h]=v;

					inqueue[v]=1;

				}

			}

		}

	}

	while (h!=t);

	if (Dist[n*2+1]==-1)

		return 0;

	return 1;

}