【费用流】洛谷1251 餐巾计划问题

今年参加BCPC暨ACM选拔的同学非常多。看了下预赛榜单，my和ljy率领一大批18级dalao，tky等buaacoding刷题狂魔也都参加了，更可怕的是还有一堆CF黄名橙名故意只写了一点点题隐藏实力。这对于你航ACM事业当然是好事，但对于我们这些菜鸡就很黑暗了。希望明天能加油，Alchemist加油~

不废话了，来看这题。如果不告诉我是网络流，我估计还真的很难想到它的算法。但告诉我是网络流之后，构图依旧不是很容易。一开始想着，拿每一天当边，拿快洗，慢洗，等待，当做状态点；后来又想到每一天的拆点——白天和晚上，超级源点连接白天供应新餐巾，然后两点间连接r[i]的边，快洗慢分别从某天晚上到另一天上午，延迟等待则从某天晚上到下一天晚上，这样连边，然后跑费用流，求出最小费用就是答案了。看起来很美好也很合理，但是实际上跑的时候就发现不对劲了。费用流首先要满足最大流。最大流此时显然是所用餐巾数的总和，此时每天的餐巾使用量才能达到要求。
然而，发现容量为r[i]的边满流时，可能此时不是最大流，但是此时费用更小。也就是可能不是最大流依旧满足题意。但是费用流要强制变成最大流，这可为之奈何？
无奈之下看了题解的构图方式，现在还没完全理解，感觉还是有些玄妙的，说不出具体的含义。叙述如下

1.超级源点连接白天点，权值为INF，费用为p
2.白天点连接超级汇点，权值为r[i]，费用为0
3.超级源点连接黑夜点，权值为r[i]，费用为0
4.黑夜点连接下一天黑夜点，权值为INF，费用为0
5.黑夜点连向m天之后的快洗边，权值为INF，费用为f
6.黑夜点连向n天之后的慢洗边，权值为INF，费用为s

大概可以这样想，首先，如果完全不考虑旧的餐巾，只有新的餐巾，显然只有1和2两类边。现在考虑旧餐巾，则5和6为原来的新餐巾提供新的来源，做出旧餐巾的替换。然后呢，因为每天产生或者提供的旧餐巾也是有上限的，所以就有了3。最后考虑旧餐巾的传递问题，就有了4。（好吧其实我没完全想明白）
MCMF我又用的是汝佳的模板~

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
using LL=long long;

const int maxn=4005;

struct Edge
{
	int from,to;
	LL cap,flow,cost;
};

struct MCMF
{
	int n,m,s,t;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool inq[maxn];
	int p[maxn];
	LL d[maxn],a[maxn];
	
	void init(int n)
	{
		this->n=n;
		for(int i=0;i<n;i++)
			G[i].clear();
		edges.clear();
	}
	
	void AddEdge(int from, int to, int cap, int cost)
	{
		edges.push_back((Edge){from,to,cap,0,cost});
		edges.push_back((Edge){to,from,0,0,-cost});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	bool BellmanFord(int s, int t, LL &flow, LL &cost)
	{
		for(int i=0;i<n;i++)
			d[i]=1E18,inq[i]=false;
		d[s]=0,inq[s]=true,p[s]=0,a[s]=1E18;
		queue<int> Q;
		Q.push(s);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			inq[u]=false;
			for(int i=0;i<G[u].size();i++)
			{
				Edge &e=edges[G[u][i]];
				if(e.cap>e.flow&&d[e.to]>d[u]+e.cost)
				{
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to])
					{
						Q.push(e.to);
						inq[e.to]=true;
					}
				}
			}
		}
		if(d[t]==1E18)
			return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s)
		{
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	
	LL Mincost(int s, int t)
	{
		LL flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost))
		printf(""); 
		return cost;
	}
}X;

int N,r[2005],p,m,f,n,s;

int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&r[i]);
	scanf("%d%d%d%d%d",&p,&m,&f,&n,&s);
	X.init(2*N+2);
	for(int i=1;i<=N;i++)
	{
		X.AddEdge(0,i,r[i],0);
		X.AddEdge(i+N,2*N+1,r[i],0);
	}
	for(int i=1;i<=N;i++)
	{
		X.AddEdge(0,i+N,1E9,p);
		if(i+m<=N)
			X.AddEdge(i,i+N+m,1E9,f);
		if(i+n<=N)
			X.AddEdge(i,i+n+N,1E9,s);
		if(i+1<=N)
			X.AddEdge(i,i+1,1E9,0);
	}
	printf("%lld",X.Mincost(0,2*N+1));
	return 0;
}

【费用流】洛谷1251 餐巾计划问题

相关推荐