首页 > 代码库 > 【BZOJ1221】【HNOI2001】软件开发 [费用流]
【BZOJ1221】【HNOI2001】软件开发 [费用流]
软件开发
Time Limit: 10 Sec Memory Limit: 162 MB[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.
Output
最少费用
Sample Input
8 2 1 6
Sample Output
HINT
1≤f,fA,fB≤60，1≤n≤1000
Main idea
每天要用Ni块餐巾，有如下几种选择：
1.买新的，每块f元；
2.用A方式处理，a天后得到餐巾，每块花费fA元；
3.用B方式处理，b天后得到餐巾，每块花费fB元。
问满足要求的最小花费。
Solution
显然是费用流，拆成两个点，Xi表示用完的，Yi表示需要的，那么建模显然：（令x表示这天需要多少餐巾）
S->Xi 流量为x，费用为0， mean：这天需要这么多；
Yi->T 流量为x，费用为0， mean：这天需要这么多；
S->Yi 流量为INF，费用为f， mean：全部买新的；
Xi->Xi+1 流量为INF，费用为0， mean：把这天用完的餐巾放到下一天处理；
Xi->Yi+a+1 流量为INF，费用为fA， mean：用A方式处理；
Xi->Yi+b+1 流量为INF，费用为fB， mean：用B方式处理。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 1000001;12 const int EDG = 1000001;13 const int INF = 2147483640;14 15 int n,a,b,f,fA,fB;16 int x;17 int X[ONE],Y[ONE];18 int S,T;19 int next[EDG],first[ONE],go[EDG],from[EDG],pas[EDG],w[EDG],tot;20 int dist[ONE],pre[ONE],vis[ONE];21 int tou,wei,q[ONE];22 int Ans;23 24 inline int get()25 {26 int res=1,Q=1; char c;27 while( (c=getchar())<48 || c>57)28 if(c==‘-‘)Q=-1;29 if(Q) res=c-48; 30 while((c=getchar())>=48 && c<=57) 31 res=res*10+c-48;32 return res*Q; 33 }34 35 void Add(int u,int v,int flow,int z)36 {37 next[++tot]=first[u]; first[u]=tot; go[tot]=v; from[tot]=u; pas[tot]=flow; w[tot]=z;38 next[++tot]=first[v]; first[v]=tot; go[tot]=u; from[tot]=v; pas[tot]=0; w[tot]=-z;39 }40 41 bool Bfs()42 {43 for(int i=S;i<=T;i++) dist[i] = INF;44 dist[S] = 0; vis[S] = 1;45 tou = 0; wei = 1; q[1] = S;46 while(tou < wei)47 {48 int u = q[++tou];49 for(int e=first[u]; e; e=next[e])50 {51 int v = go[e];52 if(dist[v] > dist[u] + w[e] && pas[e])53 {54 dist[v] = dist[u] + w[e]; pre[v] = e;55 if(!vis[v])56 {57 vis[v] = 1;58 q[++wei] = v;59 }60 }61 }62 vis[u] = 0;63 }64 return dist[T] != INF;65 }66 67 void Deal()68 {69 int x = INF;70 for(int e=pre[T]; e; e=pre[from[e]]) x = min(x,pas[e]);71 for(int e=pre[T]; e; e=pre[from[e]])72 {73 pas[e] -= x;74 pas[((e-1)^1)+1] += x;75 Ans += x*w[e];76 }77 }78 79 int main()80 {81 n=get(); a=get(); b=get();82 f=get(); fA=get(); fB=get();83 S=0; T=n*2+5;84 for(int i=1;i<=n;i++) X[i]=i, Y[i]=i+n;85 for(int i=1;i<=n;i++)86 {87 x = get();88 Add(S,X[i], x,0);89 Add(Y[i],T, x,0);90 Add(S,Y[i], INF,f);91 if(i!=n) Add(X[i],X[i+1], INF,0);92 if(Y[i]+a+1 < T)Add(X[i],Y[i]+a+1, INF,fA);93 if(Y[i]+b+1 < T)Add(X[i],Y[i]+b+1, INF,fB);94 }95 96 while(Bfs()) Deal();97 printf("%d",Ans);98 99 }
【BZOJ1221】【HNOI2001】软件开发 [费用流]