首页 > 代码库 > bzoj1221: [HNOI2001] 软件开发
bzoj1221: [HNOI2001] 软件开发
1221: [HNOI2001] 软件开发
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1351 Solved: 748
[Submit][Status][Discuss]
Description
某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。
Input
第1行为n,a,b,f,fA,fB. 第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）
Output
最少费用
Sample Input
4 1 2 3 2 1
8 2 1 6
8 2 1 6
Sample Output
38
HINT
Source
1. 源点到第i天的入点连容量ni费用为0的边
2. 第i天的出点到汇点连容量ni费用为0的边
3. 源点到第i天的出点连容量为INF费用为f的边（保证每天的出点到汇点满流）
4. 第i天的入点到第i+a+1(i+b+1)天的出点连容量为INF费用为fa(fb)的边（代表两种消毒方式）
5. 第i天的入点到第i+1天的入点连容量为INF费用为0的边（代表每天剩下的毛巾可以留到下一天）
1 #include<bits/stdc++.h> 2 #define inf 2147483647 3 #define rep(i,l,r) for(int i=l;i<=r;i++) 4 #define N 10050 5 using namespace std; 6 struct Edge{ 7 int to,next,from,c,w; 8 }e[5000000]; 9 int head[N],tot=1,ans,dis[N],from[N],r[N],n,T,a,b,f,fa,fb,c,s[N];10 bool used[N];11 inline void ins(int u,int v,int w,int cost) {12 e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; e[tot].c=cost; e[tot].from=u;13 }14 inline void insert(int u,int v,int w,int cost) {15 ins(u,v,w,cost); ins(v,u,0,-cost);16 }17 inline bool spfa() {18 queue<int> q; for(int i=0;i<=T;i++) dis[i]=inf; dis[0]=0; q.push(0); used[0]=1; 19 while(!q.empty()) {20 int x=q.front(); q.pop();21 for(int k=head[x];k;k=e[k].next) 22 if(e[k].w>0&&dis[x]+e[k].c<dis[e[k].to]){23 dis[e[k].to]=dis[x]+e[k].c; from[e[k].to]=k;24 if(!used[e[k].to]) {25 used[e[k].to]=1; q.push(e[k].to);26 }27 }28 used[x]=0;29 }30 if(dis[T]==inf) return 0;else return 1;31 }32 33 inline void run() {34 int x=inf;35 for(int k=from[T];k;k=from[e[k].from]) x=min(x,e[k].w);36 for(int k=from[T];k;k=from[e[k].from]) {37 e[k].w-=x; e[k^1].w+=x; ans+=e[k].c*x;38 }39 }40 41 inline int read() {42 int x=0; char ch=getchar();43 while(ch<‘0‘ || ch>‘9‘) ch=getchar();44 while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();45 return x;46 }47 int main () {48 scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);49 T=n+n+1;50 rep(i,1,n) scanf("%d",&s[i]);51 rep(i,1,n) insert(0,i,s[i],0),insert(i+n,T,s[i],0),insert(0,i+n,inf,f);52 rep(i,1,n-1) insert(i,i+1,inf,0);53 rep(i,1,n) {54 if(i+a<n) insert(i,i+n+a+1,inf,fa);55 if(i+b<n) insert(i,i+n+b+1,inf,fb);56 } 57 while(spfa()) run();58 printf("%d",ans);59 }
bzoj1221: [HNOI2001] 软件开发
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。