光棱坦克¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
未来科技公司为光棱坦克装上了增强激光发射器和超时空链路，准备到尤里的前哨基地做一次实地演示。激光能够沿建筑间的路径折射，链路则可以提前阻断其中一些路径。
原型机造价不菲，又没有其他部队掩护。演示只有一次开火的机会，随后就得撤离。董事长已经准备好了宣传稿，现在只差一个经得起计算的“最大期望伤害”。
形式化问题描述¶
给定 \(n\) 个顶点和 \(e\) 条无向边组成的森林，顶点编号为 \(1\) 到 \(n\) . 顶点 \(i\) 被击中时产生伤害 \(d_i\) ，其折射概率为 \(p_i\) .
攻击前，每个顶点可以选择至多 \(b\) 条与它相连的边进行阻断。一条边只要被任意一个端点选中，就会被阻断；它仅占用主动选择该边的端点的名额。随后选择一个顶点作为初始攻击点。
每个顶点至多被击中一次。顶点 \(i\) 被击中后，令 \(C\) 为沿未被阻断的边与它相邻、且尚未被击中的顶点集合：
- 若 \(C\) 为空，该顶点不再向其他顶点折射。
- 否则，以 \(p_i\) 的概率击中 \(C\) 中所有顶点；以 \(1-p_i\) 的概率从 \(C\) 中等概率选择一个顶点击中。
- 新击中的顶点继续按同样规则折射，各次随机选择相互独立。
总伤害为所有被击中顶点的 \(d_i\) 之和。攻击点和全部阻断选择均在随机过程开始前确定。设最优策略的期望总伤害为 \(V\) ，输入给定的取整偏移量为 \(\delta\) ，输出 \(\lfloor V+\delta+0.5\rfloor\) .
输入格式¶
第一行依次包含顶点数 \(n\) 、每个顶点的阻断名额 \(b\) 、边数 \(e\) 和取整偏移量 \(\delta\) . 前三项为整数，最后一项为实数。
接下来 \(e\) 行，每行两个整数 \(u,v\) ，表示一条边。
接下来一行包含 \(n\) 个实数 \(d_1,\ldots,d_n\) .
最后一行包含 \(n\) 个实数 \(p_1,\ldots,p_n\) .
输出格式¶
输出一个整数，即 \(\lfloor V+\delta+0.5\rfloor\) .
样例 1¶
输入¶
3 1 2 0.00
3 2
1 3
1.00 2.00 3.00
0.500 0.500 0.800
输出¶
6
解释¶
不阻断路径并攻击顶点 \(1\) ，三个顶点都会被击中，总伤害为 \(6\) .
样例 2¶
输入¶
6 0 5 0.50
2 3
4 6
4 3
1 2
2 5
1.00 2.00 3.00 4.00 5.00 6.00
0.500 0.500 0.500 0.500 0.500 0.500
输出¶
20
解释¶
攻击顶点 \(6\) 时依次击中 \(6,4,3,2\) ，其伤害之和为 \(15\) . 在顶点 \(2\) 处，以相同概率击中剩余两个顶点，或等概率选择其中一个，因此这一步的期望伤害为 \(0.5\times(1+5)+0.5\times(1+5)/2=4.5\) . 此时总期望 \(19.5\) 为所有策略中的最大值；加入 \(\delta=0.50\) 并取整，得到 \(20\) .
样例 3¶
输入¶
5 1 4 0.00
1 2
1 3
1 4
1 5
0.00 10.00 9.00 0.00 0.00
0.000 0.000 0.000 0.000 0.000
输出¶
19
解释¶
让顶点 \(4\) 选择阻断边 \((1,4)\) ，顶点 \(5\) 选择阻断边 \((1,5)\) . 每个顶点都没有超过一个名额，顶点 \(1\) 也不需要为这两条边消耗名额。
随后攻击顶点 \(2\) ，激光依次击中 \(2,1,3\) ，总伤害为 \(19\) . 这已经等于所有顶点的伤害之和，因此最优。
数据范围与保证¶
- \(1\le n\le2000\) ，\(0\le e\le n-1\) ，\(0\le b\le e\) .
- \(1\le u,v\le n\) ；没有自环、重边或环，允许不连通。
- \(0\le d_i\le5000\) ，\(0\le p_i\le1\) ，\(0\le\delta\le1\) .
- \(d_i\) 和 \(\delta\) 至多两位小数，\(p_i\) 至多三位小数。
- 设 \(z=V+\delta\) ，保证 \(\lvert z-\lfloor z+0.5\rfloor\rvert\le0.3\) ，即结果远离取整分界。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |