a428: NOI2008 Day2.1.奥运物流
Tags :
Accepted rate : 9人/9人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:20

Content

2008 北京奥运会即将开幕,举国上下都在为这一盛事做好准备。为了高效率、
成功地举办奥运会,对物流系统进行规划是必不可少的。

物流系统由若干物流基站组成,以1…N 进行编号。每个物流基站i 都有且
仅有一个后继基站Si,而可以有多个前驱基站。基站i 中需要继续运输的物资都
将被运往后继基站Si,显然一个物流基站的后继基站不能是其本身。编号为1 的
物流基站称为控制基站,从任何物流基站都可将物资运往控制基站。注意控制基
站也有后继基站,以便在需要时进行物资的流通。在物流系统中,高可靠性与低
成本是主要设计目。对于基站i,我们定义其“可靠性”R(i)如下:

设物流基站i 有w 个前驱基站P1,P2,...Pw,即这些基站以i 为后继基站,则基
站i 的可靠性R(i)满足下式:

R(i)=Ci+k ∑R(Pj) ,这里1≤j≤w。

其中Ci 和k 都是常实数且恒为正,且有k 小于1。

整个系统的可靠性与控制基站的可靠性正相关,我们的目标是通过修改物流
系统,即更改某些基站的后继基站,使得控制基站的可靠性R(1)尽量大。但由于
经费限制,最多只能修改m 个基站的后继基站,并且,控制基站的后继基站不
可被修改。因而我们所面临的问题就是,如何修改不超过m 个基站的后继,使
得控制基站的可靠性R(1)最大化。

Input
输入第一行包含两个整数与一个实数,N, m, k。其中N 表示基
站数目,m 表示最多可修改的后继基站数目,k 分别为可靠性定义中的常数。
第二行包含N 个整数,分别是S1, S2…SN,即每一个基站的后继基站编号。
第三行包含N 个正实数,分别是C1, C2…CN,为可靠性定义中的常数。
Output
输出仅包含一个实数,为可得到的最大R(1)。精确到小数点两位。
Sample Input
4 1 0.5
2 3 1 3
10.0 10.0 10.0 10.0
Sample Output
30.00
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :

原有物流系统如左图所示,4 个物流基站的可靠性依次为22.8571,21.4286,
25.7143,10。

最优方案为将2 号基站的后继基站改为1 号,如右图所示。 此时4 个基站
的可靠性依次为30,25,15,10。

对于所有的数据,满足 m ≤ N ≤ 60,Ci ≤ 10^6,0.3 ≤ k < 1。

Tags:
出處:
NOI2008Day2第一题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」