首页 > 其他分享 >P4480 餐厅计划问题

P4480 餐厅计划问题

时间:2023-09-26 17:25:23浏览次数:51  
标签:cnt P4480 int ll 毛巾 long edge 计划 餐厅

前置

注意,网络流不是这道题的正解,学习正解的可以看看别人的题解。

所需知识:费用流。

分析

首先考虑这个网络流如何建边,毕竟最难的地方还是建边。

网络流拆点成边的技巧有很多种,在这里推荐一道题目。

P2045 方格取数加强版

根据题意,可以进行以下的操作。

  1. 购买毛巾。
  2. 将毛巾放到 \(A\) 店去洗,并在 \(m_1\) 天后获得毛巾。
  3. 将毛巾放到 \(B\) 店去洗,并在 \(m_2\) 天后获得毛巾。
  4. 以后再来洗。

注意操作四是很容易忽略掉的,但是需要考虑进去,虽然你现在不需要毛巾,但是可能以后需要。

将每一天拆成两个点然后连边,也就是说,钱就是费用,毛巾的需求量就是单价。

所以就有如下的代码。

code-建边

	s=0,t=2*n+1;//s是起始点,t是终点
	for(int i=1;i<=n;i++)
	{
		ll u;
		cin>>u;
		add(s,i,u,0);//表示终点给起始点脏毛巾。
		add(i+n,t,u,0);//表示起始点给终点干净毛巾。
	}
	for(int i=1;i<=n;i++)
	{
		add(s,i+n,inf,p);
		if(i+1<=n) add(i,i+1,inf,0);//这里三个之所以加判断条件,是因为如果毛巾没拿到n天就结束了,肯定是没有用的。   
		if(i+a<=n) add(i,i+n+a,inf,f); 
		if(i+b<=n) add(i,i+n+b,inf,ss); 
	}

剩下的就只需要跑一遍 dinic 就得到了答案。由于流量是无限大的(就是可以源源不断的获得毛巾),所以后面四个的建边流量是 \(inf\)。

关于代码效率

我用的是 SPFA 来跑,关于 SPFA 他死了,似乎有很多玄学的方法优化,但是在这里就不在赘述。

不过还是有代码实现的。在这道题确实提高了挺多效率,如果是大常数选手可以考虑。关于 long long 和 memset 不要滥用,这样还是可以通过此题的。dinic 需要考虑当前弧优化。

玄学优化效率普通 SPFA 效率

最后给出第二种代码的实现方式。

code

#include<bits/stdc++.h>
#define ll long long
#define next _
const ll inf=1e17;
using namespace std;
const int N=4e6+50;
long long n,p,b,f,a,ss,tot,ans,s;
ll d[N];
int head[N],to[N],c[N],next[N];
long long edge[N],cost[N];
queue<int>q;
bool v[N];
int cnt=1;
int t,num;
void add(int x,int y,register ll w,int f)
{
	to[++cnt]=y;next[cnt]=head[x];edge[cnt]=w;cost[cnt]=f;head[x]=cnt;
	to[++cnt]=x;next[cnt]=head[y];edge[cnt]=0;cost[cnt]=-f;head[y]=cnt;
}
bool spfa()
{
	for(int i=0;i<=t;i++) d[i]=inf,v[i]=0,c[i]=head[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=head[k];i;i=next[i])
		{
			int u=to[i],w=cost[i];
			if(d[u]>d[k]+w&&edge[i])
			{
				d[u]=d[k]+w;
				if(!v[u]) v[u]=1,q.push(u); 
			} 
		}
	}
	return d[t]!=inf;
}
ll dfs(int p,ll now)
{
	if(p==t||!now)	return now;
	ll minn=0,used=0;
	v[p]=1;
	for (int i=c[p];i;i=next[i])
	{
		c[p]=i; int u=to[i],w=cost[i];
		if((!v[u]||u==t)&&d[u]==d[p]+w&&edge[i])
		if((minn=dfs(u,min(now-used,edge[i]))))
		{
			edge[i]-=minn; edge[i^1]+=minn; used+=minn;
			tot+=w*minn;
		}
		if(used==now)	break;
	}
	v[p]=0;
	return used;
}
long long dinic()
{
	while (spfa())
	{
        memcpy(c,head,(t+1)*sizeof(int));
		dfs(s,inf);
	}
	return tot;
}
signed main()
{
	scanf("%lld",&n);
	scanf("%lld%lld%lld%lld%lld",&a,&b,&f,&ss,&p);
	s=0,t=2*n+1;
	for(int i=1;i<=n;i++)
	{
		ll u;
		cin>>u;
		add(s,i,u,0);
		add(i+n,t,u,0);
	}
	for(int i=1;i<=n;i++)
	{
		add(s,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,ss); 
	}
	cout<<dinic();
}

标签:cnt,P4480,int,ll,毛巾,long,edge,计划,餐厅
From: https://www.cnblogs.com/onlyfiee/p/17730692.html

相关文章

  • (10/1-10/31)10月摸鱼计划,挑战7/14/21天发博文,实体礼品包邮送!
    10月摸鱼计划,来啦!本月继续以【博主任务】形式,让大家自发选择更文任务!任务达标后即可兑奖!且任务间的奖品可同享!【活动时间】发文时间:2023年10月1日—2023年10月31日【活动任务】以下任务福利可同享!!任务一:7天更文任务要求任务链接任务奖品7天发布文章(可以非连续)发文直达>>https://blo......
  • 阅读计划
    阅读书目:《代码大全》和《需求分析与系统设计》计划阅读笔记发表时间:第一篇:2023-09-25第二篇:2023-09-27第三篇:2023-10-05第四篇:2023-10-07第五篇:2023-10-14第六篇:2023-10-21第七篇:2023-10-28第八篇:2023-11-04第九篇:2023-11-11第十篇:2023-11-18......
  • 2023年大三上阅读计划
    阅读书目:《代码大全》和《需求分析与系统设计》计划阅读笔记发表时间:第一篇:2023-09-25第二篇:2023-09-27第三篇:2023-10-05第四篇:2023-10-07第五篇:2023-10-14第六篇:2023-10-21第七篇:2023-10-28第八篇:2023-11-04第九篇:2023-11-11第十篇:2023-11-18......
  • 阅读计划
    《软件需求十步走》阅读笔记发布时间:9月25号、10月25号、11月25号、12月25号《需求分析与系统设计》阅读笔记发布时间:10月5号·、11月5号、12月5号《实例化需求》阅读笔记发布时间:10月15号、11月15号、12月15号......
  • 2023秋季阅读笔记计划
    1、目标阅读的书籍名称《代码大全》、《梦断代码》2、目标阅读笔记的发表时间第一篇:2023-09-24第二篇:2023-09-27第三篇:2023-09-30第四篇:2023-10-03第五篇:2023-10-09第六篇:2023-10-15第七篇:2023-10-21第八篇:2023-10-27第九篇:2023-11-03第十篇:2023-11-08......
  • 阅读计划
    9月:《软件工程:一种实践方法》,读后感分别于9月26日、9月28日、9月30日发布10月:《敏捷软件开发宣言》,读后感分别于10月4日、10月14日、10月21日发布11月:《软件工程导论》,读后感分别于11月5日、11月14日、11月24日发布12月:《架构师之路:软件架构之美》,读后感分别于12月8日、12月......
  • 阅读计划
    10月《用户故事与敏捷方法》读后感分别于10月7日、10月15日、10月23日发布11月《软件需求最佳实践》读后感分别于11月7日、11月15日、11月23日发布12月《敏捷软件开发宣言》读后感分别于12月7日、12月15日、12月23日发布......
  • 读书计划
    计划一个月读一本书《SoftwareDesignX-Rays》据说是关于软件工程最重要的一本书。书中作者展示了许多技术(大部分是基于版本控制系统的数据)用于识别热点,复杂性趋势,耦合,或者重构。所有的材料都匹配了相应的例子,参考资料和一些有趣的图例。读完这本书后,你可能会问自己:如何做到......
  • 大三上学期读书计划
    9月:《构建之法---现代软件工程》读后感分别于9月26日、9月28日、9月30日发布10月:《大话软件工程-需求分析与软件设计》读后感分别于10月5日、10月15日、10月25日发布11月:《人件》读后感分别于11月5日、11月14日、11月24日发布12月:《智能与数据重构世界》读后感分别于12月10日......
  • 阅读计划
    9月:《软件工程:一种实践方法》,读后感分别于9月26日、9月28日、9月30日发布10月:《敏捷软件开发宣言》,读后感分别于10月4日、10月14日、10月21日发布11月:《软件工程导论》,读后感分别于11月5日、11月14日、11月24日发布12月:《架构师之路:软件架构之美》,读后感分别于12月8日、12月......