[BZOJ 1221] 软件开发

发布于2016年03月18日 | 暂无评论 | 859阅读 | 费用流

题目描述

某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

输入格式

第1行为n,a,b,f,fA,fB. 第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）

输出格式

最小费用。

题目解析

和网络流24题中“餐巾计划问题”相似。

题目的限制条件有点多，我们来逐条分析建模：

1.每天用完的毛巾和供应的毛巾的量应该是相同的，第 $i$ 天为 $n_i$ 。基于这个思想，建源 $s$ 汇 $t$ ，把天数分为 $X,Y$ 两部， $X_i$ 代表第 $i$ 天用完的， $Y_i$ 代表第 $i$ 天供应的。 $s$ 向 $X_i$ 连容量为 $n_i$ ，费用为0的边， $Y_i$ 向 $t$ 连容量为 $n_i$ ，费用为0的边。

2. $s$ 向 $Y_i$ 连容量为无穷大，费用为 $f$ 的边，表示买入的毛巾。

3. $X_i$ 向 $Y_{i+a+1}$ 连容量为无穷大，费用为 $fA$ 的边，表示A种消毒方式。

4. $X_i$ 向 $Y_{i+b+1}$ 连容量为无穷大，费用为 $fB$ 的边，表示B种消毒方式。

5. $X_i$ 向 $X_{i+1}$ 连容量为无穷大，费用为0的边，今天洗不完的毛巾明天洗。

跑最小费用最大流即可。看起来还是很显然的吧。

/**************************************************************
    Problem: 1221
    User: frank_c1
    Language: C++
    Result: Accepted
    Time:1804 ms
    Memory:1936 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=2005;
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 main() {
    int n,a,b,f,fa,fb,k;
    read(n);read(a);read(b);read(f);read(fa);read(fb);
    memset(fr,-1,sizeof(fr));
    s=0;t=1;
    REP(i,1,n) {
        read(k);
        addedge(s,i<<1,k,0);
        addedge(i<<1|1,t,k,0);
        addedge(s,i<<1|1,INF,f);
        if(i+1<=n) addedge(i<<1,(i+1)<<1,INF,0);
        if(i+a+1<=n) addedge(i<<1,(i+a+1)<<1|1,INF,fa);
        if(i+b+1<=n) addedge(i<<1,(i+b+1)<<1|1,INF,fb);
    }
    tot=n*2+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

121

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

Problem: 1221

User: frank_c1

Language: C++

Result: Accepted

Time:1804 ms

Memory:1936 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=2005;

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 main() {

int n,a,b,f,fa,fb,k;

read(n);read(a);read(b);read(f);read(fa);read(fb);

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

s=0;t=1;

REP(i,1,n) {

read(k);

addedge(s,i<<1,k,0);

addedge(i<<1|1,t,k,0);

addedge(s,i<<1|1,INF,f);

if(i+1<=n) addedge(i<<1,(i+1)<<1,INF,0);

if(i+a+1<=n) addedge(i<<1,(i+a+1)<<1|1,INF,fa);

if(i+b+1<=n) addedge(i<<1,(i+b+1)<<1|1,INF,fb);

}

tot=n*2+1;mincost();

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

return 0;

}

AC. 梦想

[BZOJ 1221] 软件开发

题目描述

输入格式

输出格式

题目解析

快速访问

随便看看

友情链接

标签