acwing1562 微博转发(宽搜)

news/2024/7/15 17:21:02 标签: 算法, 数据结构, 图论, 宽度优先

微博被称为中文版的 Twitter。

微博上的用户既可能有很多关注者,也可能关注很多其他用户。

因此,形成了一种基于这些关注关系的社交网络。

当用户在微博上发布帖子时,他/她的所有关注者都可以查看并转发他/她的帖子,然后这些人的关注者可以对内容再次转发…

现在给定一个社交网络,假设只考虑 L 层关注者,请你计算某些用户的帖子的最大可能转发量。

补充

如果 B 是 A 的关注者,C 是 B 的关注者,那么 A 的第一层关注者是 B,第二层关注者是 C。

输入格式

第一行包含两个整数,N 表示用户数量,L 表示需要考虑的关注者的层数。

假设,所有的用户的编号为 1∼N。

接下来 N 行,每行包含一个用户的关注信息,格式如下:

M[i] user_list[i]

M[i] 是第 i 名用户关注的总人数,user_list[i] 是第 i 名用户关注的 M[i] 个用户的编号列表。

最后一行首先包含一个整数 K,表示询问次数,然后包含 K 个用户编号,表示询问这些人的帖子的最大可能转发量。

输出格式

按顺序,每行输出一个被询问人的帖子最大可能转发量。

假设每名用户初次看到帖子时,都会转发帖子,只考虑 L 层关注者。

数据范围

1≤N≤1000
1≤L≤6
1≤M[i]≤100,
1≤K≤N

输入样例:

7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6

输出样例:

4
5
难度:中等
时/空限制:3s / 64MB
总通过数:1184
总尝试数:2664
来源:PAT甲级真题1076
算法标签

认真读题

 用到宽度优先搜索,以该点为根节点每次向下搜一层,即搜完该点的所有子树个数,一共搜索m层,难点在于如何实现只搜索m层?

可以预先声明一个变量sz,存储前三次搜索时入队的个数,即队列里面的元素个数,最后相加,

前三次搜索中第一次入队的是该点(根节点),意思是第m层只入队并没有出队,所以最后bfs返回的是res+q.size()-1.

一定要将判重的st数组首先memset,位置放到后面也会答案错误,这一点不清楚,懂的大佬可以解释一下

 

 

 


http://www.niftyadmin.cn/n/107572.html

相关文章

8位单片机(51 STC8)C语言处理32位unsigned long型数据之计算出错

一、问题描述 入门51没多久后就主攻32了,最近又搞起51,移植一个软定时器代码到STC8上,结果出现了奇怪的问题,而这种问题在各种32位单片机上都是不曾有的。 有如下代码,实现了软定时器。使用内部IRC,22.1184…

c语言数据结构-排序(快速+归并+计数+桶)

(创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,请留下您的足迹) 快速排序: 原理:快速排序的核心思想是设立一个轴,然后其他数据都和这个轴作比较…

47个SQL性能优化技巧,看到就是赚到

1、先了解MySQL的执行过程 了解了MySQL的执行过程,我们才知道如何进行sql优化。 (1)客户端发送一条查询语句到服务器; (2)服务器先查询缓存,如果命中缓存,则立即返回存储在缓存中的…

报名投票链接怎么做做一个投票的链接怎么做微信投票链接怎么做

近些年来,第三方的微信投票制作平台如雨后春笋般络绎不绝。随着手机的互联网的发展及微信开放平台各项基于手机能力的开放,更多人选择微信投票小程序平台,因为它有非常大的优势。1.它比起微信公众号自带的投票系统、传统的H5投票系统有可以图…

MySQL参数优化之thread_cache_size

1.thread_cache_size简介 每建立一个连接,都需要一个线程来与之匹配,此参数用来缓存空闲的线程,以至不被销毁,如果线程缓存中有空闲线程,这时候如果建立新连接,MYSQL就会很快的响应连接请求。 show statu…

【c#】学习DATATABLE排序

c#实现Datatable排序Datatable排序结果图代码展示总结Datatable排序 结果图 原数据 倒序 去重 筛选行 代码展示 1、使用datatable视图对table进行排序 //倒序排序 dt.DefaultView.Sort “CreateTime desc”; dt dt.DefaultView.ToTable(); 如果想升序排序&#xff0c…

Unity——制作简易红绿灯

效果图与该类红绿灯相似。前提准备首先在场景中,创建一个正方体(灯座),球体(作为灯),把其放置成红绿灯结构。创建四个材质球,基础色分别赋为灰色,红色,黄色&a…

实现RecyclerView二级列表

自定义RecyclerView的adapter实现二级列表 图片大于5MB,CSDN不让上传,使用github链接,如果看不到请使用科学上网 https://github.com/nanjolnoSat/PersonalProject/blob/recyclerexpandableadapter/Recyclerexpanableadapter/pic/pic1.gif 源…