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天的软件开发中,提供毛巾服务的总费用最低。

$1\leq f,fA,fB\leq 60,1\leq n\leq 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

#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%10+'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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇