P1850 [NOIP 2016 提高组] 换教室

NOIP2016 提高组 D1T3

对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中，有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i$（$1 \leq i \leq n$）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 $c_i$ 上课，而另一节课程在教室 $d_i$ 进行。 在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 $n$ 节安排好的课程。如果学生想更换第 $i$ 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 $i$ 个时间段去教室 $d_i$ 上课，否则仍然在教室 $c_i$ 上课。 由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 $i$ 节课程的教室时，申请被通过的概率是一个已知的实数 $k_i$，并且对于不同课程的申请，被通过的概率是互相独立的。 学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 $m$ 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 $m$ 门课程，也可以不用完这 $m$ 个申请的机会，甚至可以一门课程都不申请。 因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。 牛牛所在的大学有 $v$ 个教室，有 $e$ 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第 $i$（$1 \leq i \leq n-1$）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。 现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

无

无

**样例 1 说明** 所有可行的申请方案和期望收益如下： - 不作申请，耗费的体力值的期望为 $8.0$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | 无 | $1.0$ | $8$ | - 申请更换第 $1$ 个时间段的上课教室，耗费的体力值的期望为 $4.8$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | $1$ | $0.8$ | $4$ | | 无 | $0.2$ | $8$ | - 申请更换第 $2$ 个时间段的上课教室，耗费的体力值的期望为 $6.4$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | $2$ | $0.2$ | $0$ | | 无 | $0.8$ | $8$ | - 申请更换第 $3$ 个时间段的上课教室，耗费的体力值的期望为 $6.0$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | $3$ | $0.5$ | $4$ | | 无 | $0.5$ | $8$ | - 申请更换第 $1,2$ 个时间段的上课教室，耗费的体力值的期望为 $4.48$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | $1,2$ | $0.16$ | $4$ | | $1$ | $0.64$ | $4$ | | $2$ | $0.04$ | $0$ | | 无 | $0.16$ | $8$ | - 申请更换第 $1,3$ 个时间段的上课教室，耗费的体力值的期望为 $2.8$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | $1,3$ | $0.4$ | $0$ | | $1$ | $0.4$ | $4$ | | $3$ | $0.1$ | $4$ | | 无 | $0.1$ | $8$ | - 申请更换第 $2,3$ 个时间段的上课教室，耗费的体力值的期望为 $5.2$。 | 申请通过的时间段 | 出现的概率 | 耗费的体力值 | | :--------: | :----: | :----: | | $2,3$ | $0.1$ | $4$ | | $2$ | $0.1$ | $0$ | | $3$ | $0.4$ | $4$ | | 无 | $0.4$ | $8$ | 因此，最优方案为：申请更换第 $1,3$ 个时间段的上课教室。耗费的体力值的期望为 $2.8$。 **提示** 1. 道路中可能会有多条双向道路连接相同的两间教室。 也有可能有道路两端连接的是同一间教室。 2. 请注意区分 $n,m,v,e$ 的意义, $n$ 不是教室的数量, $m$ 不是道路的数量。 **数据范围与说明** | 测试点编号 | $n\le$ | $m\le$ | $v\le$ | 是否具有特殊性质 1 | 是否具有特殊性质 2 | | :--------: | :----: | :----: | :----: | :----------------: | :----------------: | | 1 | $1$ | $1$ | $300$ | $\times$ | $\times$ | | 2 | $2$ | $0$ | $20$ | $\times$ | $\times$ | | 3 | $2$ | $1$ | $100$ | $\times$ | $\times$ | | 4 | $2$ | $2$ | $300$ | $\times$ | $\times$ | | 5 | $3$ | $0$ | $20$ | $\surd$ | $\surd$ | | 6 | $3$ | $1$ | $100$ | $\surd$ | $\times$ | | 7 | $3$ | $2$ | $300$ | $\times$ | $\times$ | | 8 | $10$ | $0$ | $300$ | $\surd$ | $\surd$ | | 9 | $10$ | $1$ | $20$ | $\surd$ | $\times$ | | 10 | $10$ | $2$ | $100$ | $\times$ | $\times$ | | 11 | $10$ | $10$ | $300$ | $\times$ | $\surd$ | | 12 | $20$ | $0$ | $20$ | $\surd$ | $\times$ | | 13 | $20$ | $1$ | $100$ | $\times$ | $\times$ | | 14 | $20$ | $2$ | $300$ | $\surd$ | $\times$ | | 15 | $20$ | $20$ | $300$ | $\times$ | $\surd$ | | 16 | $300$ | $0$ | $20$ | $\times$ | $\times$ | | 17 | $300$ | $1$ | $100$ | $\times$ | $\times$ | | 18 | $300$ | $2$ | $300$ | $\surd$ | $\surd$ | | 19 | $300$ | $300$ | $300$ | $\times$ | $\surd$ | | 20 | $2000$ | $0$ | $20$ | $\times$ | $\times$ | | 21 | $2000$ | $1$ | $20$ | $\times$ | $\times$ | | 22 | $2000$ | $2$ | $100$ | $\times$ | $\times$ | | 23 | $2000$ | $2000$ | $100$ | $\times$ | $\times$ | | 24 | $2000$ | $2000$ | $300$ | $\times$ | $\times$ | | 25 | $2000$ | $2000$ | $300$ | $\times$ | $\times$ | 特殊性质 1：图上任意不同的两点 $u,v$ 间，存在一条耗费体力最少的路径只包含一条道路。 特殊性质 2：对于所有的 $1≤ i≤ n,\ k_i= 1$。