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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

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

保证 1\leq n\leq 700 1\leq m\leq 60000

输出格式

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

样例

样例输入 1
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
样例输出 1
2
样例说明 1

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

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

数据范围与提示

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

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