题目描述
某软件公司正在规划一项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.每天用完的毛巾和供应的毛巾的量应该是相同的,第
天为
。基于这个思想,建源
汇
,把天数分为
两部,
代表第
天用完的,
代表第
天供应的。
向
连容量为
,费用为0的边,
向
连容量为
,费用为0的边。
2.
向
连容量为无穷大,费用为
的边,表示买入的毛巾。
3.
向
连容量为无穷大,费用为
的边,表示A种消毒方式。
4.
向
连容量为无穷大,费用为
的边,表示B种消毒方式。
5.
向
连容量为无穷大,费用为0的边,今天洗不完的毛巾明天洗。
跑最小费用最大流即可。看起来还是很显然的吧。
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; } |