[BZOJ 2424] 订货

发布于2016年03月19日 | 暂无评论 | 1,159阅读 | 费用流

题目描述

某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。

输入格式

第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)

输出格式

只有1行，一个整数，代表最低成本。

题目解析

又是一发餐巾计划问题。

分析一下题目条件，建模如下：

1.按月数建点，设第 $i$ 月为 $X_i$ 。

2.建源 $s$ 汇 $t$ ， $s$ 向 $X_i$ 连容量为无穷大，费用为 $d_i$ 的边，表示该月订单。

3. $X_i$ 向 $t$ 连容量为 $U_i$ ，费用为0的边，表示当月的需求量。

4. $X_i$ 向 $X_{i+1}$ 连容量为 $S$ ，费用为 $m$ 的边，表示第 $i$ 月贮存下来的产品。

跑最小费用最大流即可。感觉这种类餐巾计划问题形式还是蛮统一的。

/**************************************************************
    Problem: 2424
    User: frank_c1
    Language: C++
    Result: Accepted
    Time:12 ms
    Memory:1296 kb
****************************************************************/
 
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
      
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct edge {
    int next,to,cap,cost;
};
 
const int maxn=60;
const int INF=(int)(1e9);
int fr[maxn];
edge e[maxn*20];
int d[maxn],a[maxn],p[maxn];
bool inq[maxn];
int tot,s,t,fl,cs,tote=-1;
 
inline void addone(int u,int v,int c,int s) {
    ++tote;
    e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;
    e[tote].cap=c;e[tote].cost=s;
}
inline void addedge(int u,int v,int c,int s) {
    addone(u,v,c,s);addone(v,u,0,-s);
    //printf("%d %d %d %d\n",u,v,c,s);
}
 
queue<int> Q;
bool SPFA() {
    REP(i,0,tot) d[i]=INF;
    Q.push(s);inq[s]=1;a[s]=INF;d[s]=0;
    while(!Q.empty()) {
        int x=Q.front();Q.pop();
        inq[x]=0;
        RAL(i,x) if(e[i].cap && d[e[i].to]>d[x]+e[i].cost) {
            d[e[i].to]=d[x]+e[i].cost;
            a[e[i].to]=min(a[x],e[i].cap);
            p[e[i].to]=i;
            if(!inq[e[i].to]) {
                Q.push(e[i].to);
                inq[e[i].to]=1;
            }
        }
    }
    if(d[t]==INF) return 0;
    fl+=a[t];
    cs+=a[t]*d[t];
    int x=t;
    while(x!=s) {
        e[p[x]].cap-=a[t];
        e[p[x]^1].cap+=a[t];
        x=e[p[x]^1].to;
    }
    return 1;
}
 
void mincost() {
    fl=cs=0;while(SPFA());
}
 
int D[60],U[60];
int main() {
    int n,m,mx;
    read(n);read(m);read(mx);
    memset(fr,-1,sizeof(fr));
    s=0;t=1;
    REP(i,1,n) read(U[i]);
    REP(i,1,n) read(D[i]);
    REP(i,1,n) {
        addedge(s,i+1,INF,D[i]);
        addedge(i+1,t,U[i],0);
        if(i+1<=n) addedge(i+1,i+2,mx,m);
    }
    tot=n+1;mincost();
    printf("%d\n",cs);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

/**************************************************************

Problem: 2424

User: frank_c1

Language: C++

Result: Accepted

Time:12 ms

Memory:1296 kb

****************************************************************/

#include <set>

#include <map>

#include <queue>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <bitset>

#include <cstring>

#include <cstdlib>

#include <utility>

#include <iostream>

#include <algorithm>

#define REP(i,a,b) for(int i=(a);i<=(b);i++)

#define PER(i,a,b) for(int i=(a);i>=(b);i--)

#define RVC(i,S) for(int i=0;i<(S).size();i++)

#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

template<class T> inline

void read(T& num) {

bool start=false,neg=false;

char c;

num=0;

while((c=getchar())!=EOF) {

if(c=='-') start=neg=true;

else if(c>='0' && c<='9') {

start=true;

num=num*10+c-'0';

} else if(start) break;

}

if(neg) num=-num;

}

/*============ Header Template ============*/

struct edge {

int next,to,cap,cost;

};

const int maxn=60;

const int INF=(int)(1e9);

int fr[maxn];

edge e[maxn*20];

int d[maxn],a[maxn],p[maxn];

bool inq[maxn];

int tot,s,t,fl,cs,tote=-1;

inline void addone(int u,int v,int c,int s) {

++tote;

e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;

e[tote].cap=c;e[tote].cost=s;

}

inline void addedge(int u,int v,int c,int s) {

addone(u,v,c,s);addone(v,u,0,-s);

//printf("%d %d %d %d\n",u,v,c,s);

}

queue<int> Q;

bool SPFA() {

REP(i,0,tot) d[i]=INF;

Q.push(s);inq[s]=1;a[s]=INF;d[s]=0;

while(!Q.empty()) {

int x=Q.front();Q.pop();

inq[x]=0;

RAL(i,x) if(e[i].cap && d[e[i].to]>d[x]+e[i].cost) {

d[e[i].to]=d[x]+e[i].cost;

a[e[i].to]=min(a[x],e[i].cap);

p[e[i].to]=i;

if(!inq[e[i].to]) {

Q.push(e[i].to);

inq[e[i].to]=1;

}

if(d[t]==INF) return 0;

fl+=a[t];

cs+=a[t]*d[t];

int x=t;

while(x!=s) {

e[p[x]].cap-=a[t];

e[p[x]^1].cap+=a[t];

x=e[p[x]^1].to;

}

return 1;

}

void mincost() {

fl=cs=0;while(SPFA());

}

int D[60],U[60];

int main() {

int n,m,mx;

read(n);read(m);read(mx);

memset(fr,-1,sizeof(fr));

s=0;t=1;

REP(i,1,n) read(U[i]);

REP(i,1,n) read(D[i]);

REP(i,1,n) {

addedge(s,i+1,INF,D[i]);

addedge(i+1,t,U[i],0);

if(i+1<=n) addedge(i+1,i+2,mx,m);

}

tot=n+1;mincost();

printf("%d\n",cs);

return 0;

}

AC. 梦想

[BZOJ 2424] 订货

题目描述

输入格式

输出格式

题目解析

快速访问

随便看看

友情链接

标签