#1707. 「THUPC 2019」改善生活 / improve

「THUPC 2019」改善生活 / improve

题目描述

「改善生活」是小 Z 创建的一个群聊。在群聊里,小 Z 和他的 n1n-1 个朋友们(共 nn 名群友,小 Z 的编号为 11,他的朋友们的编号从 22nn)无话不说,畅谈甚欢。然而,经常水群会被冠以水王的名号,这让小 Z 头痛不已。

今天,小 Z 预见到了群里可能会有 nn 个话题(编号分别为 1n1\ldots n)。其中,第 ii 个话题是 cic_i 号群友(当然也有可能是小 Z 自己)感兴趣的话题,这意味着该话题如果出现,这位群友将会进行 wiw_i 分钟的激烈发言。方便起见,你可以认为,除此之外,群友不会进行激烈发言。

所有 nn 个话题之间有 mm 组引导关系,每组引导关系的形式是一个二元组 (u,v)(u,v),它表示如果 uu 号话题出现,必定会导致 vv 号话题出现。

巧合的是,小 Z 发现,所有他自己的不同话题都不存在直接或间接的引导关系。

由于期中考试的临近,除小 Z 外的群友们都忙于复习,因此他们不会主动发起话题(发起话题指让一个话题出现,下同),也就是说,所有 ci1c_i\neq 1 的话题都只能由引导关系直接或间接引出。这让想要水群、却又希望摆脱水王名号的小 Z 左右为难。因此,他决定主动发起一个或以上自己感兴趣的话题,来诱导其他话题的出现,致使水群最多的另一位群友激烈发言的时间小 Z 自己激烈发言的时间的比值尽可能大。即最大化下面这个式子:

$$\frac{\max\limits_{k=2}^n \operatorname{sum}(k)}{\operatorname{sum}(1)} $$

其中,sum(k)\operatorname{sum}(k) 表示所有出现群友 kk 感兴趣的话题的 ww 值总和。

为避免精度误差,你只需要求出最大值向下取整的结果即可。

输入格式

第一行两个正整数 n,mn,m,分别表示话题数(恰好也是群人数)、引导关系组数。

第二行 nn 个正整数 c1,,cnc_1,\dots, c_n1cin1\leq c_i\leq n),依次描述对各话题感兴趣的群友编号。保证至少存在一个ii 使得 ci=1c_i=1

第三行 nn 个正整数 w1,,wnw_1,\dots, w_n1wi1001\leq w_i\leq 100),依次描述各话题感兴趣的群友将激烈发言的时间。

接下来 mm 行描述引导关系,每行两个正整数 u,vu,v1u,vn1\leq u,v\leq n),描述一组引导关系 (u,v)(u,v),具体意义见【题目描述】,保证所有不同的 ci=1c_i=1 的话题之间两两不存在直接或间接的引导关系

对于每一行,如果行内包含多个数,则用单个空格将它们隔开。

保证 1n7001\leq n\leq 7001m600001\leq m\leq 60000

输出格式

一行一个整数,表示所求式子最大值向下取整的结果,即不超过该值的最大整数。

样例

7 8
2 2 1 1 3 3 4
100 100 40 20 100 50 40
1 3
2 3
1 4
2 4
3 5
4 6
3 7
4 7
2

小 Z 可以选择发起编号为 3 和 4 的话题,这将致使编号为 5、6、7 的话题出现,并引发 3 号群友时长 150150 分钟的激烈发言、以及 4 号群友时长 4040 分钟的激烈发言。由于 33 号群友激烈发言时间更长,且小 Z 自己的激烈发言时长为 6060 分钟,因此所求最大比值为 15060=2.5\frac{150}{60}=2.5,这个值向下取整的结果是 22

可以证明小 Z 不存在更优的策略。

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。