首页 > 代码库 > BZOJ 1221 HNOI 2001 软件开发/网络流24题 餐巾计划问题 最小费用最大流
BZOJ 1221 HNOI 2001 软件开发/网络流24题 餐巾计划问题 最小费用最大流
题目大意:有一个软件公司,每天需要给一些员工准备消毒毛巾,这些毛巾可以循环利用,但是需要消毒。可以将毛巾送去消毒,有两种方式,A天fA花费,B天fB花费。或者还可以直接买新毛巾,问为了满足员工的需求,至少需要花多少钱。
思路:经典的费用流问题。将每一天拆点,S向每一天<<1连边,约束每一天需要多少毛巾;每一天<<1|1向T连边,约束每一天需要的毛巾。每一天<<1向这一天清洗的毛巾能够使用的那一天<<1|1,注意A和B。毛巾可以延后使用,那么每一天<<1|1向(每一天+1)<<1|1连边,表示延后使用。然后跑EK。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 2010 #define MAXE 100000 #define INF 0x3f3f3f3f #define S 0 #define T (MAX - 1) using namespace std; #define max(a,b) ((a) > (b) ? (a):(b)) struct MinCostMaxFlow{ int head[MAX],total; int next[MAXE],aim[MAXE],flow[MAXE],cost[MAXE]; int from[MAX],p[MAX],f[MAX]; bool v[MAX]; MinCostMaxFlow():total(1) {} void Add(int x,int y,int f,int c) { next[++total] = head[x]; aim[total] = y; flow[total] = f; cost[total] = c; head[x] = total; } void Insert(int x,int y,int f,int c) { Add(x,y,f,c); Add(y,x,0,-c); } bool SPFA() { static queue<int> q; memset(f,0x3f,sizeof(f)); memset(v,false,sizeof(v)); while(!q.empty()) q.pop(); q.push(S); f[S] = 0; while(!q.empty()) { int x = q.front(); q.pop(); v[x] = false; for(int i = head[x]; i; i = next[i]) if(flow[i] && f[aim[i]] > f[x] + cost[i]) { f[aim[i]] = f[x] + cost[i]; if(!v[aim[i]]) { v[aim[i]] = true; q.push(aim[i]); } from[aim[i]] = x; p[aim[i]] = i; } } return f[T] != INF; } int EdmondsKarp() { int re = 0; while(SPFA()) { int max_flow = INF; for(int i = T; i != S; i = from[i]) max_flow = min(max_flow,flow[p[i]]); for(int i = T; i != S; i = from[i]) { flow[p[i]] -= max_flow; flow[p[i]^1] += max_flow; } re += f[T] * max_flow; } return re; } }Solver; int days,buy_cost,slow,slow_cost,fast,fast_cost; int main() { cin >> days >> slow >> fast >> buy_cost >> slow_cost >> fast_cost; ++slow,++fast; for(int x,i = 1; i <= days; ++i) { scanf("%d",&x); Solver.Insert(S,i << 1,x,0); Solver.Insert(i << 1|1,T,x,0); Solver.Insert(S,i << 1|1,INF,buy_cost); } for(int i = 1; i <= days; ++i) { if(i + slow <= days) Solver.Insert(i << 1,(i + slow) << 1|1,INF,slow_cost); if(i + fast <= days) Solver.Insert(i << 1,(i + fast) << 1|1,INF,fast_cost); } for(int i = 1; i < days; ++i) Solver.Insert(i << 1|1,(i + 1) << 1|1,INF,0); cout << Solver.EdmondsKarp() << endl; return 0; }
BZOJ 1221 HNOI 2001 软件开发/网络流24题 餐巾计划问题 最小费用最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。