首页 > 试题广场 >

珂朵莉喊你一声大佬

[编程题]珂朵莉喊你一声大佬
  • 热度指数：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
算法知识视频讲解
开通博客
头像 鞋儿破，帽儿破，身上的袈裟破
发表于 2020-08-18 11:55:05
首先由题意可以知道， 该图不一定连通， 可能是好几个图， 但是一定是特殊的树形结构， 即根节点和叶节点可能是一个环。这时候运用tarjan缩点后重新建图， 就会建成树形结构（可能是好几颗树）。然后二分（二分最小的大佬数量）剩下的就是check的问题了check要用到DFS回溯和拓扑排序DFS不能从根 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ZZZYM
发表于 2022-02-22 18:14:45
珂朵莉喊你一声大佬(tarjan求强连通分量并缩点+二分) 思路 本题中，每个点最多只有一条入边, 构成一个类似外向树森林的图。不了解外向树的可以搜索基环树(又称环套树)，外向树是基环树的一种，每个结点有且仅有一条入边。又因为本题中的点至多有一条入边,可能没有入边，所以是类似外向树，严格来说不是外 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 张广文
发表于 2020-03-23 20:38:25
include include include include include define LL long long using namespace std;const int N=1e6+77;int n,m,f[N],F[N],a[N],cnt,b[N];int head[N],nxt[2N] 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

珂朵莉喊你一声大佬

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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