【BZOJ】1221: [HNOI2001] 软件开发(最小费用最大流)

时间:2023-03-09 06:53:54
【BZOJ】1221: [HNOI2001] 软件开发(最小费用最大流)

http://www.lydsy.com/JudgeOnline/problem.php?id=1221

先吐槽一下,数组依旧开小了RE;在spfa中用了memset和<queue>的版本TE;自己写的循环队列没有>2000我只是写的是==2000 WA。T_T_T_T_T_T_T_T呜呜呜呜呜~~

【BZOJ】1221: [HNOI2001] 软件开发(最小费用最大流)

坑坑坑坑坑。

说一下做法吧:

将每天拆成2个点,xi和yi,xi表示当天用完的,yi表示当天需要的,那么很容易看出xi>=当天人数,yi==当天人数

一开始我觉得一定是上下界的。。。(这东西太神奇,不会做),后来看了题解发现下界巧妙的转化了。。。待会说。

首先建图:

从源连一条弧到yi,容量为oo,费用为f,表示每天需要的都能够通过买来补给。

从xi连一条弧到xi+1,容量为oo,费用为0,表示当天用完的不做处理,可以留到第二天。(注意边界

从xi连一条弧到yi+a,容量为oo,费用为fa,表示当天用完的(包括之前没有处理的传上来的)的一些或全部进行A消毒,并且提供给第i+a天。(注意边界)

从xi连一条弧到yi+b,容量为oo,费用为fb,表示当天用完的(包括之前没有处理的传上来的)的一些或全部进行B消毒,并且提供给第i+b天。(注意边界)

从源连一条弧到xi,容量为当天人数,费用为0,表示当天用完的一些毛巾或者全部毛巾丢给xi(因为可能在当天将毛巾丢掉了,即后面一条弧的含义)

从yi连一条弧到汇,容量为当天人数,费用为0,表示当天用完的一些毛巾或者全部毛巾全部丢掉。。

然后跑一次最小费用最大流即可,(zkw费用流有必要学啊,,spfa太慢了。。。)

#include <cstdio>
#include <cstring>
using namespace std;
#define CC(a, b) memset(a, b, sizeof(a))
#define min(a,b) ((a)<(b)?(a):(b))
const int N=2100, M=1000001, oo=1000000000;
int ihead[N], inext[M], from[M], to[M], cap[M], cost[M], cnt=1;
int d[N], p[N];
bool vis[N];
int q[N], front, tail; void add(int u, int v, int c, int m) {
inext[++cnt]=ihead[u]; ihead[u]=cnt; from[cnt]=u; to[cnt]=v; cap[cnt]=c; cost[cnt]=m;
inext[++cnt]=ihead[v]; ihead[v]=cnt; from[cnt]=v; to[cnt]=u; cap[cnt]=0; cost[cnt]=-m;
} bool spfa(const int &s, const int &t, const int &n) {
int i, u;
for(i=0; i<=n; ++i) d[i]=oo, vis[i]=0;
d[s]=front=tail=0; vis[s]=1;
q[tail++]=s;
while(front!=tail) {
u=q[front++]; if(front==2001) front=0;
for(i=ihead[u]; i; i=inext[i]) if(cap[i] && d[to[i]]>d[u]+cost[i]) {
d[to[i]]=d[u]+cost[i];
p[to[i]]=i;
if(!vis[to[i]]) {
vis[to[i]]=1;
q[tail++]=to[i]; if(tail==2001) tail=0;
}
}
vis[u]=0;
}
return d[t]!=oo;
} int mincost(const int &s, const int &t, const int &n) {
int ret=0, f, u;
while(spfa(s, t, n)) {
for(f=oo, u=t; u!=s; u=from[p[u]]) f=min(f, cap[p[u]]);
for(u=t; u!=s; u=from[p[u]]) cap[p[u]]-=f, cap[p[u]^1]+=f;
ret+=d[t]*f;
}
return ret;
} int main() {
int n, a, b, f, fa, fb, i, r;
scanf("%d%d%d%d%d%d", &n, &a, &b, &f, &fa, &fb);
int s=0, t=(n<<1)+1;
for(i=1; i<=n; ++i) {
if(i+1<=n) add(i, i+1, oo, 0);
if(i+a+1<=n) add(i, n+i+a+1, oo, fa);
if(i+b+1<=n) add(i, n+i+b+1, oo, fb);
add(0, n+i, oo, f);
}
for(i=1; i<=n; ++i) {
scanf("%d", &r);
add(s, i, r, 0);
add(n+i, t, r, 0);
}
printf("%d\n", mincost(s, t, t+1));
return 0;
}

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

Sample Output

38

HINT

Source