AC. 梦想

frank_c1

[BZOJ 1221] 软件开发

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

题目描述

某软件公司正在规划一项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的边，今天洗不完的毛巾明天洗。

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

BZOJ1221
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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;
}

快速访问

    分类目录：

    文章归档：

随便看看

标签

Copyright © 2016 AC. 梦想 版权所有 | Powered By WordPress | Theme By YeLook