LuoguP2223 [HNOI2001]软件开发 题解
Description
某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。
1leq f,fA,fBleq 60,1leq nleq 1000
Solution
首先，拆点，把每个点拆成入点和出点，分别为 i 和 i n。
考虑每天有且只有 n_i 个毛巾，故建立超级源点 S 和超级汇点 T，并在 S 和 i 之间、i n 和 T 之间连接容量 inf，费用 0 的边。
接下来考虑各个方法。
对于 a 和 b 只要在 i 天和 i a 天之间连一条容量为 inf，费用为 fa 的边，b 同理。
每天的新毛巾可以留到明天，所以 i 和 i 1 之间连接一条容量为 inf，费用为 0 的边。
最后每天可以进货，所以 S 和 i n 连 inf,f。
最后跑一遍费用流。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=1010;
int n,a,b,f,fa,fb,c[N],cnt,S,T,in[N],out[N],inf=2e9,fir[N<<1],son[N<<4],nxt[N<<4],w[N<<4],cost[N<<4],tot=1,dis[N<<1],vis[N<<1],Cost;
I void add(CI x,CI y,CI z,CI c){nxt[ tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c;}
#define Add(x,y,z,c) (add(x,y,z,c),add(y,x,0,-c))
queue<int> q;
#define to son[i]
struct Edge{int son,id;}pre[N<<1];
I bool bfs(){
W(!q.empty()) q.pop();memset(dis,63,sizeof(dis));inf=dis[0];dis[S]=0;memset(vis,0,sizeof(vis));q.push(S);W(!q.empty()){
RI u=q.front(),i;q.pop();for(i=fir[u];i;i=nxt[i]) if(w[i]>0&&dis[to]>dis[u] cost[i]) dis[to]=dis[u] cost[i],
pre[to]=(Edge){u,i},!vis[to]&&(q.push(to),vis[to]=1);vis[u]=0;
}return dis[T]<inf;
}
I void EK(){
Cost=0;W(bfs()){
RI i,Min=inf;for(i=T;i^S;i=pre[i].son) Min=min(Min,w[pre[i].id]);
for(i=T;i^S;i=pre[i].son) w[pre[i].id]-=Min,w[pre[i].id^1] =Min;
Cost =Min*dis[T];
}return ;
}
int main(){
RI i;for(S= cnt,T= cnt,read(n,a,b,f,fa,fb),i=1;i<=n;i ) read(c[i]),in[i]= cnt,out[i]= cnt,Add(S,in[i],c[i],0),Add(out[i],T,c[i],0),Add(S,out[i],inf,f);
for(a ,b ,i=1;i<=n;i ) i a<=n&&(Add(in[i],out[i a],inf,fa),0),i b<=n&&(Add(in[i],out[i b],inf,fb),0),i<n&&(Add(in[i],in[i 1],inf,0),0);
return EK(),writeln(Cost),0;
}
