[luogu3356]:[网络流24题]火星探险问题

Description

火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。

给定每个位置的状态,计算探测车的最优移动方案,使到达传送器的探测车的数量最多,

而且探测车采集到的岩石标本的数量最多

阅读更多

[luogu2770]:[网络流24题]航空路线问题

Description

给定一张航空图,图中顶点代表城市,边代表 2 城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

(1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。

(2)除起点城市外,任何城市只能访问 1 次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

阅读更多

[bzoj1070]:[SCOI2007]修车

Description

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

阅读更多

[bzoj3961]:[WF2011]Chips Challenge

Description

一位著名的微处理器公司邀请您帮忙在他们的电脑芯片上安排一些组件,每个芯片被设计成拥有N × N个插槽的正方形。一个插槽可以存放一个组件,你要尽可能多地在芯片上安装组件。
现代的处理器设计是相当复杂的。不幸地,你需要满足以下的限制。
* 一些插槽是不可用的
* 一些插槽已经被其他的组件所占据,无法用于固定额外的组件。
* 芯片水平和垂直边界上连接着着一些内存总线,他们的带宽负载需要匹配。也就是说,第一行和第一列的组件数目必须一样多,第二行和第二列的组件数目必须一样多,依此类推。这里的组件数要包括之前已经存在于芯片之上和后来加上去的。
* 类似地,每行每列都有能量供应系统。为了避免局部过热,对于给定的一组A,B,任何一行/一列的组件数都不能超过总组件数的A / B。
你希望计算出最多可以在芯片上再安装多少个组件。

阅读更多

[luogu1251]:[网络流24题] 餐巾计划问题

Description

一个餐厅在相继的N天里,第i天需要Ri块餐巾(i=l,2,…,N)。餐厅可以从三种途径获得餐巾。

(1)购买新的餐巾,每块需p分;

(2)把用过的餐巾送到快洗部,洗一块需m天,费用需f分(f<p)。如m=l时,第一天送到快洗部的餐巾第二天就可以使用了,送慢洗的情况也如此。

(3)把餐巾送到慢洗部,洗一块需n天(n>m),费用需s分(s<f)。

在每天结束时,餐厅必须决定多少块用过的餐巾送到快洗部,多少块送慢洗部。在每天开始时,餐厅必须决定是否购买新餐巾及多少,使洗好的和新购的餐巾之和满足当天的需求量Ri,并使N天总的费用最小

阅读更多