b996: NOIP2016 Day1.3.换教室
Tags :
Accepted rate : 5人/5人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-02-21 11:53

Content

对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中,有2n节课程安排在n个时间段上。在第i (1 <= i <= n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室ci上课,而另一节课程在教室di进行。

在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室,则需要提出申请。若申请通过,学生就可以在第i个时间段去教室di上课,否则仍然在教室ci上课。

由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第i节课程的教室时,申请被通过的概率是一个已知的实数ki,并且对于不同课程的申请,被通过的概率是互相独立的。

学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多m节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的m门课程,也可以 不用完 这m个申请的机会,甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有v个教室,有e条道路。每条道路连接两间教室,并且是可以 双向通行 的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。当第i (1<= i <= n-1)节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的 路径 前往下一节课的教室。

现在牛牛想知道,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的 期望值 最小,请你帮他求出这个最小值。

Input

第一行四个整数n, m, v, e。n表示这个学期内的时间段的数量;m表示牛牛最多可以申请更换多少节课程的教室;v表示牛牛学校里教室的数量;e表示牛牛的学校里道路的数量。

第二行n个正整数,第i (1 <= i<= n)个正整数表示ci,即第i个时间段牛牛被安排上课的教室;保证1 <= Ci <= v。

第三行n个正整数,第i (1<=i<=n)个正整数表示di,即第i个时间段另一间上同样课程的教室;保证1<=di<=v。

第四行n个实数,第i (1<=i<=n)个实数表示ki,即牛牛申请在第i个时间段更换教室获得通过的概率。保证0 <= ki <= 1。

接下来e行,每行三个正整数aj,bj,wj,表示有一条双向道路连接教室aj,bj,通过这条道路需要耗费的体力值是wj;保证1 <= aj, bj <= v, 1 <= wj <= 100。

保证 1 <= n <= 2000,0 <= m <= 2000, 1 <= v <= 300, 0 <= e <= 90000。

保证通过学校里的道路,从任何一间教室出发,都能到达其他所有的教室。

保证输入的实数最多包含3位小数。

Output

输出一行,包含一个实数,四舍五入精确到小数点后 恰好2位 ,表示答案。你的输出必须和标准输出 完全一样 才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于4 x 10^-3。(如果你不知道什么是浮点误差,这段话可以理解为:对于大多数的算法,你可以正常地使用浮点数类型而不用对它进行特殊的处理)

Sample Input #1
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
Sample Output #1
2.80
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (4%): 1.0s , <1M
公開 測資點#1 (4%): 1.0s , <1M
公開 測資點#2 (4%): 1.0s , <1K
公開 測資點#3 (4%): 1.0s , <1M
公開 測資點#4 (4%): 1.0s , <1M
公開 測資點#5 (4%): 1.0s , <1M
公開 測資點#6 (4%): 1.0s , <1M
公開 測資點#7 (4%): 1.0s , <1M
公開 測資點#8 (4%): 1.0s , <1M
公開 測資點#9 (4%): 1.0s , <1M
公開 測資點#10 (4%): 1.0s , <1M
公開 測資點#11 (4%): 1.0s , <1M
公開 測資點#12 (4%): 1.0s , <1M
公開 測資點#13 (4%): 1.0s , <1M
公開 測資點#14 (4%): 1.0s , <1M
公開 測資點#15 (4%): 1.0s , <1M
公開 測資點#16 (4%): 1.0s , <1M
公開 測資點#17 (4%): 1.0s , <1M
公開 測資點#18 (4%): 1.0s , <1M
公開 測資點#19 (4%): 1.0s , <1M
公開 測資點#20 (4%): 1.0s , <1M
公開 測資點#21 (4%): 1.0s , <1M
公開 測資點#22 (4%): 1.0s , <1M
公開 測資點#23 (4%): 1.0s , <1M
公開 測資點#24 (4%): 1.0s , <1M
Hint :

所有可行的申请方案和期望收益如下表:

申请更换教室的时间段申请通过的时间段出现的概率耗费的体力值耗费的体力值的期望
1.088.0
110.844.8
0.28
220.206.4
0.88
330.546.0
0.58
1、21、20.1644.48
10.644
20.040
0.168
1、31、30.402.8
10.44
30.14
0.18
2、32、30.145.2
20.10
30.44
0.48

 

【提示】

  1. 道路中可能会有多条双向道路连接相同的两间教室。也有可能有道路两端连接的是 同一间 教室。
  2. 请注意区分n,m,v,e的意义,n 不是 教室的数量,m 不是 道路的数量。

【子任务】

测试点nmv特殊性质1特殊性质2
1≤1≤1≤300××
2≤2≤0≤20
3≤1≤100
4≤2≤300
5≤3≤0≤20
6≤1≤100×
7≤2≤300×
8≤10≤0
9≤1≤20×
10≤2≤100×
11≤10≤300
12≤20≤0≤20×
13≤1≤100×
14≤2≤300
15≤20×
16≤300≤0≤20×
17≤1≤100
18≤2≤300
19≤300×
20≤2000≤0≤20×
21≤1
22≤2≤100
23≤2000
24≤300
25

特殊性质1:图上任意两点 ai,bi (ai≠bi)间,存在一条耗费体力最少的路径只包含一条道路。

特殊性质2:对于所有的 1≤i≤n,ki=1。

Tags:
出處:
NOIP2016提高组Day1第三题 [管理者:
liouzhou_101 (王启圣)
]


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