2424: [HAOI2010]订货
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1483 Solved: 998
[Submit][Status][Discuss]
Description
某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。
Input
第1行：n, m, S (0<=n<=50, 0<=m<=10, 0<=S<=10000)
第2行：U1 , U2 , … , Ui , … , Un (0<=Ui<=10000)
第3行：d1 , d2 , …, di , … , dn (0<=di<=100)
Output
只有1行，一个整数，代表最低成本
Sample Input
3 1 1000
2 4 8
1 2 4
Sample Output
34
很明显的费用流。
对于每一个仓库只有两种情况，要么从S点进货，要么从上个月的剩余货物转移。
每个点向汇点T连流量为Ui，费用为0的边，限制每个月所需货物。S向每个点连流量为inf，费用为di的边，然后每个i向i+1连剩余货物转移的边，流量为s即可。
EK:
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2010,M=1e6+10;
int n,m,S,d[N],v[N],e[N],s,t;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
to[++tot]=b; nex[tot]=head[a]; w[tot]=d; flow[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,0,-d);}
inline int spfa(){
memset(d,inf,sizeof d); int vis[N]={0}; vis[s]=1; d[s]=0;
queue<int> q; q.push(s);
while(q.size()){
int u=q.front(); q.pop(); vis[u]=0;
for(int i=head[u];i;i=nex[i]){
if(flow[i]&&d[to[i]]>d[u]+w[i]){
d[to[i]]=d[u]+w[i];
v[to[i]]=u; e[to[i]]=i;
if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
}
}
}
return d[t]!=inf;
}
int EK(){
int res=0;
while(spfa()){
int mi=inf;
for(int i=t;i!=s;i=v[i]) mi=min(mi,flow[e[i]]);
for(int i=t;i!=s;i=v[i]) flow[e[i]]-=mi,flow[e[i]^1]+=mi;
res+=d[t]*mi;
}
return res;
}
signed main(){
scanf("%d %d %d",&n,&m,&S); t=2001;
for(int i=1,x;i<=n;i++) scanf("%d",&x),add(i,t,x,0);
for(int i=1,x;i<=n;i++) scanf("%d",&x),add(s,i,inf,x);
for(int i=1;i<n;i++) add(i,i+1,S,m);
printf("%d\n",EK());
return 0;
}
zkw：
AC代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2010,M=1e6+10;
int n,m,S,d[N],vis[N],st[N],s,t,res;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
to[++tot]=b; nex[tot]=head[a]; flow[tot]=c; w[tot]=d; head[a]=tot;
}
inline void add(int a,int b,int c,int d){ade(a,b,c,d); ade(b,a,0,-d);}
inline int spfa(){
memset(st,0,sizeof st); queue<int> q; q.push(s);
memset(d,0x3f,sizeof d); d[s]=0; vis[s]=1;
while(q.size()){
int u=q.front(); q.pop(); vis[u]=0;
for(int i=head[u];i;i=nex[i]){
if(flow[i]&&d[to[i]]>d[u]+w[i]){
d[to[i]]=d[u]+w[i];
if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
}
}
}
return d[t]<inf;
}
int dfs(int x,int f){
if(x==t) return res+=f*d[t],f;
st[x]=1; int fl=0;
for(int i=head[x];i&&f;i=nex[i]){
if(flow[i]&&!st[to[i]]&&d[to[i]]==d[x]+w[i]){
int mi=dfs(to[i],min(flow[i],f));
flow[i]-=mi; flow[i^1]+=mi; fl+=mi; f-=mi;
}
}
return fl;
}
inline int zkw(){
while(spfa()) dfs(s,inf); return res;
}
signed main(){
scanf("%d %d %d",&n,&m,&S); t=2001;
for(int i=1,x;i<=n;i++) scanf("%d",&x),add(i,t,x,0);
for(int i=1,x;i<=n;i++) scanf("%d",&x),add(s,i,inf,x);
for(int i=1;i<n;i++) add(i,i+1,S,m);
printf("%d\n",zkw());
return 0;
}
京公网安备 11010502036488号