首页 > 代码库 > 【bzoj1221】[HNOI2001] 软件开发 费用流
【bzoj1221】[HNOI2001] 软件开发 费用流
题目描述
某软件公司正在规划一项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）
输出
最少费用
样例输入
4 1 2 3 2 1
8 2 1 6
样例输出
38
题解
费用流
本题和 网络流24题-餐巾计划问题 极为相似，唯一不同的是本题中消毒的实际相差时间为消耗时间+1
建图方法：
每个点拆成2个，分别为xi和yi。
S->xi，容量为ni，费用为0；yi->T，容量为ni，费用为0；S->yi，容量为ni（inf也一样），费用为f；
xi->xi+1，容量为inf，费用为0；xi->yi+a+1，容量为inf，费用为fa；xi->yi+b+1，容量为inf，费用为fb。
比较正经的理解方法：
将xi看作脏毛巾，将yi看作干净的毛巾。由于每天买毛巾的价格相同，所以一定是洗完或买完毛巾就立刻使用，所以yi直接向t连边。
每天能够得到ni条脏毛巾，这些脏毛巾不一定立刻送洗，所以xi想xi+1连边，表示留到下一天。
比较不正经的理解方法：
将xi看作脏毛巾，将yi看作干净的毛巾，要求每天需要ni条干净的毛巾，所以为有上下界费用流，因此原本应有边yi->xi，容量下界为ni，上界也为ni，费用为0。
其余的按照正常方法建图。
建图之后转化成一般费用流解决，发现图和上面的是一样的。
#include <cstdio>#include <cstring>#include <queue>#define N 2500#define M 100000#define inf 0x7fffffffusing namespace std;queue<int> q;int head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , from[N] , pre[N];void add(int x , int y , int v , int c){ to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){ int x , i; memset(from , -1 , sizeof(from)); memset(dis , 0x3f , sizeof(dis)); dis[s] = 0 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) if(val[i] && dis[to[i]] > dis[x] + cost[i]) dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]); } return ~from[t];}int mincost(){ int ans = 0 , i , k; while(spfa()) { k = inf; for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]); ans += k * dis[t]; for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k; } return ans;}int main(){ int n , a , b , f , fa , fb , i , x; scanf("%d%d%d%d%d%d" , &n , &a , &b , &f , &fa , &fb) , s = 0 , t = 2 * n + 1; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , add(s , i , x , 0) , add(i + n , t , x , 0) , add(s , i + n , inf , f); for(i = 1 ; i < n ; i ++ ) add(i , i + 1 , inf , 0); for(i = 1 ; i <= n - a - 1 ; i ++ ) add(i , i + a + 1 + n , inf , fa); for(i = 1 ; i <= n - b - 1 ; i ++ ) add(i , i + b + 1 + n , inf , fb); printf("%d\n" , mincost()); return 0;}
【bzoj1221】[HNOI2001] 软件开发 费用流