前置
注意,网络流不是这道题的正解,学习正解的可以看看别人的题解。
所需知识:费用流。
分析
首先考虑这个网络流如何建边,毕竟最难的地方还是建边。
网络流拆点成边的技巧有很多种,在这里推荐一道题目。
根据题意,可以进行以下的操作。
- 购买毛巾。
- 将毛巾放到 \(A\) 店去洗,并在 \(m_1\) 天后获得毛巾。
- 将毛巾放到 \(B\) 店去洗,并在 \(m_2\) 天后获得毛巾。
- 以后再来洗。
注意操作四是很容易忽略掉的,但是需要考虑进去,虽然你现在不需要毛巾,但是可能以后需要。
将每一天拆成两个点然后连边,也就是说,钱就是费用,毛巾的需求量就是单价。
所以就有如下的代码。
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 需要考虑当前弧优化。
最后给出第二种代码的实现方式。
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