[HNOI2001] 软件开发
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1938 Solved: 1118
[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
题解：这个和网络流24题里的餐巾纸那道题一样的，有一个
显然的贪心，没必要多买，然后
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue> #define N 1007
#define inf 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,a,b,f,fa,fb,S,T;
bool boo[N<<];
int dis[N<<];
int cnt=,hed[N<<],nxt[N<<],rea[N<<],val[N<<],fee[N<<];
struct Node
{
int e,fa;
void init()
{
e=fa=-;
}
}e[N<<]; void add(int u,int v,int z,int w)
{
nxt[++cnt]=hed[u];
hed[u]=cnt;
rea[cnt]=v;
val[cnt]=z;
fee[cnt]=w;
}
void add_two_way(int u,int v,int z,int w)
{
add(u,v,z,w);
add(v,u,,-w);
}
bool Spfa()
{
for (int i=S;i<=T;i++)
dis[i]=inf,e[i].init(),boo[i]=false;
queue<int>q;
q.push(S);boo[S]=true,dis[S]=;
while(!q.empty())
{
int u=q.front();q.pop();
for (int i=hed[u];i!=-;i=nxt[i])
{
int v=rea[i],cost=fee[i];
if (dis[v]>dis[u]+cost&&val[i]>)
{
dis[v]=dis[u]+cost;
e[v].fa=u,e[v].e=i;
if (!boo[v])
{
boo[v]=true;
q.push(v);
}
}
}
boo[u]=false;
}
if (dis[T]!=inf) return true;
else return false;
}
int mfmc()
{
int ans=;
while(Spfa())
{
int x=inf;
for (int i=T;e[i].fa!=-;i=e[i].fa)
x=min(x,val[e[i].e]);
ans+=dis[T]*x;
for (int i=T;e[i].fa!=-;i=e[i].fa)
val[e[i].e]-=x,val[e[i].e^]+=x;
}
return ans;
}
int main()
{
memset(hed,-,sizeof(hed));
n=read(),a=read(),b=read(),f=read(),fa=read(),fb=read();
S=,T=n*+;
for (int i=;i<=n;i++)
{
if (i+a+<=n) add_two_way(i,i+n+a+,inf,fa);
if (i+b+<=n) add_two_way(i,i+n+b+,inf,fb);
if (i+<=n) add_two_way(i,i+,inf,);
}
for (int i=;i<=n;i++)
{
int x=read();
add_two_way(S,i,x,);
add_two_way(S,i+n,x,f);
add_two_way(i+n,T,x,);
}
printf("%d\n",mfmc());
}