BZOJ-2424: [HAOI2010]订货【费用流】
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1487 Solved: 1002
[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
2 4 8
1 2 4
Sample Output
34
HINT
Source
思路：建立超级源和超级汇，令每条连向超级汇的边代价为0、cap为当月需求量，连向超级源的边cap无穷大，代价为当月进货价，每月之间连的边cap为仓库容量，代价为每天贮存花销。
建图后跑MCMF
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 2001; const int inf = 0x3f3f3f3f; int n,m,s; int cnt = 1; int ans; int from[2005],q[2005],dis[2005],head[2005]; bool inq[2005]; template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; } struct node { int from,to,next,v,c; }e[1000001]; void add(int u,int v,int w,int c) { cnt++; e[cnt].from = u; e[cnt].to = v; e[cnt].v = w; e[cnt].c = c; e[cnt].next = head[u]; head[u] = cnt; } void BuildGraph(int u,int v,int w,int c) { add(u,v,w,c); add(v,u,0,-c);///反向 } bool spfa() { for(int i = 0; i <= maxn; i++)dis[i]=inf; int t = 0, w = 1, now; dis[0] = q[0] = 0; inq[0] = 1; while(t != w) { now = q[t]; t++; if(t == maxn) t = 0; for(int i = head[now]; i; i = e[i].next) { if(e[i].v && dis[e[i].to] > dis[now] + e[i].c) { from[e[i].to] = i; dis[e[i].to] = dis[now] + e[i].c; if(!inq[e[i].to]) { inq[e[i].to] = 1; q[w++] = e[i].to; if(w == maxn) w = 0; } } } inq[now] = 0; } if(dis[maxn] == inf) return 0; return 1; } void mcmf()///最小费用最大流 { int i; int x = inf; i = from[maxn]; while(i) { x = min(e[i].v,x); i = from[e[i].from]; } i = from[maxn]; while(i) { e[i].v -= x; e[i^1].v += x; ans += x * e[i].c; //printf("ans : %d\n",ans); i = from[e[i].from]; } } int main() { read(n),read(m),read(s); for(int i = 1; i <= n; i++) { int u; read(u); BuildGraph(i, maxn, u, 0); } for(int i = 1; i <= n; i++) { int d; read(d); BuildGraph(0, i, inf, d); } for(int i = 1; i < n; i++) { BuildGraph(i, i+1, s, m); } while(spfa()) { mcmf(); } printf("%d",ans); return 0; }
投递美团等公司9个岗位