首页 > 试题广场 >

珂朵莉喊你一声大佬

[编程题]珂朵莉喊你一声大佬
  • 热度指数：4 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

有n种大佬，第i种大佬有ai个
珂朵莉想让最少个数的一种大佬的个数最多
你可以创造m个任意种类的大佬，并且可以把一些大佬变成另一些大佬
x -> y意味着可以把任意个x类型的大佬变成y类型的大佬
一个大佬可以被转换多次
对于每个y，最多有一个x使得x -> y成立



输入描述:
第一行两个数n,m
之后一行，第i个数xi表示第i种大佬可以被哪种大佬转换得到
如果xi为-1表示这种大佬不可以被任何大佬转换得到
之后一行，第i个数ai表示第i种大佬的个数


输出描述:
输出一行一个数表示答案
答案即
你要求让最少个数的一种大佬的个数最多的方案
输出这个方案下最少个数的一种大佬的个数
示例1

输入

5 5
-1 1 1 1 1 
4 5 1 3 2

输出

3
示例2

输入

10 10
-1 1 1 2 1 5 5 6 10 5 
6 1 7 1 7 1 10 5 1 1

输出

4

备注:
对于100%的数据，n <=1000000 , m , ai <= 1000000000
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

二分 拓扑排序
上传者：牛客301599号
难度：
0条回答 22浏览

热门推荐

通过挑战的用户

查看代码

相关试题

珂朵莉喊你一声大佬

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号