[文章目录]
Description
某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。n<=50,m<=10
费用流水题。每天建一个节点，每天节点向后连边，容量为s，价格为m。远点向每个节点连边，流量为inf，价格为d。每天节点向汇点连边，容量为u。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t,S,ans;
const int inf=0x3f3f3f3f;
int head[60],to[410],nxt[410],f[410],w[410],cnt=1;
void add(int x,int y,int ff,int ww)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=ff; w[cnt]=ww;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0; w[cnt]=-ww;
}
queue<int>q;
int dis[60],path[60];
bool v[60];
bool spfa()
{
while(!q.empty()) q.pop();
memset(dis,0x3f,sizeof dis);
memset(v,0,sizeof v);
q.push(s); dis[s]=0; v[s]=1; int x;
while(!q.empty())
{
x=q.front(); q.pop(); v[x]=0;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]>dis[x]+w[i])
{
dis[to[i]]=dis[x]+w[i];
path[to[i]]=i^1;
if(!v[to[i]]) q.push(to[i]),v[to[i]]=1;
}
}
return dis[t]<inf;
}
void mincost()
{
while(spfa())
{
int tmp=inf;
for(int i=t;i!=s;i=to[path[i]]) tmp=min(tmp,f[path[i]^1]);
for(int i=t;i!=s;i=to[path[i]])
{
ans+=tmp*w[path[i]^1];
f[path[i]]+=tmp; f[path[i]^1]-=tmp;
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&S);
s=n+1,t=s+1;
int i,x;
for(i=1;i<n;++i) add(i,i+1,S,m);
for(i=1;i<=n;++i)
{
scanf("%d",&x);
add(i,t,x,0);
}
for(i=1;i<=n;++i)
{
scanf("%d",&x);
add(s,i,inf,x);
}
mincost();
printf("%d",ans);
return 0;
}