PAT (Advanced Level) Practice 1076 Forwards on Weibo (30 分)_pat advancedlevel1076 深度搜索-程序员宅基地

技术标签: PAT甲级 (Advanced Level) Practic  C++  

  • 编程题

1076 Forwards on Weibo (30 分)

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤1000), the number of users; and L (≤6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format:

M[i] user_list[i]

where M[i] (≤100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space.

Then finally a positive K is given, followed by K UserID's for query.

Output Specification:

For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can triger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.

Sample Input:

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

Sample Output:

4
5

题目大意:

给出节点总数和每个节点的多个单向目标节点,求某个节点的L层反向目标节点个数。

解题思路:

使用BFS广度优先搜索。

读入每个节点的单向目标节点并记录。

用book数组记录每个节点的层数。用广搜求一共有多少个符合要求的节点。

注意事项:

1、有关层数计算,广搜优于深搜。试了深搜,有两个测试点没过,还没找到原因。

2、在判断层数是否符合要求时,需要在每个节点的循环中判断,而不是在某个节点的循环完成后再判断。(如果每次循环完成后level++再判断,这个level值是错误的,答案也不就不对了。)对BFS的层序遍历还需要更加熟悉。

源代码:

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
struct node
{
	vector<int>follower;
};
vector<node>v;
int cnt, n, l, book[1002];
/*
void dfs(int i, int level)
{
	if (level == l)return;
	for (int j=0; j<v[i].follower.size(); j++)
	{
		if (book[v[i].follower[j]] == 0)
		{
			book[v[i].follower[j]] = 1;
			cnt++;
			dfs(v[i].follower[j], level + 1);
		}
	}
	return;
}
*/
void bfs(int i)
{
	queue<int>q;
	int level = 0;
	q.push(i);
	while (!q.empty())
	{
		int temp = q.front();
		for (int j = 0; j < v[temp].follower.size(); j++)
		{
			if (book[v[temp].follower[j]] == 0&&book[temp]<=l)
			{
				book[v[temp].follower[j]] = book[temp]+1;
				q.push(v[temp].follower[j]);
				cnt++;
			}
		}
		q.pop();
	}
	return;
}
int main()
{
	int i, j, k, fl;
	scanf("%d %d", &n, &l);
	v.resize(n + 1);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &k);
		for (j = 0; j < k; j++)
		{
			scanf("%d", &fl);
			v[fl].follower.push_back(i);
		}
	}
	scanf("%d", &k);
	for (i = 0; i < k; i++)
	{
		for (j = 1; j <= n; j++)book[j] = 0;
		scanf("%d", &fl);
		book[fl] = 1;
		cnt = 0;
//		dfs(fl, 0);
		bfs(fl);
		printf("%d\n", cnt);
	}
	system("pause");
	return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yi976263092/article/details/84112928

智能推荐

主流流媒体服务器软件,十款免费的流媒体服务器软件介绍-程序员宅基地

文章浏览阅读4.7k次。互联网时代,服务器是网络的重要支撑,大家租用云服务器除了搭建网站服务器之外,还会用到搭建其他各种WEB应用服务器,而流媒体服务器的搭建就是其中一种,那么应该怎么进行流媒体服务器的搭建呢?你知道有那些免费的流媒体服务器软件吗?(你可能想知道:视频流媒体服务器的选择方式?)流媒体服务器是指提供以流方式在网络中传送音频、视频和多媒体文件的媒体形式服务的服务器。它的主要功能是流式协议(RTP/RTSP、M..._流媒体服务器软件

java文件流上传文件,Java:通过HTTP流式传输Zipfile的内容-程序员宅基地

文章浏览阅读662次。I have quite some amount of streamable data (>100MB), which, for the sake of compression, i would like to host packed in a zipfile on an http-server. So this zipfile contains a single file.Now is i..._java 用httputil 以文件流的形式上传文件

mysql mvcc undo_UNDO及MVCC、崩溃恢复-程序员宅基地

文章浏览阅读129次。避免脏读、事务回滚、非阻塞读、MVCC、崩溃恢复redo前滚、undo回滚危害、判断、处理实现undo分离、收缩undo表空间0、undo物理存储研究1>ibdata第五个数据块(系统事务表)中存储着128个undo段的段头块的地址2>每一个undo段头块有1024行,两行记录一个事务,一共可以记录512个事务3>一个数据行中存放XID、rollpointr4>一个数据行被..._mysql一直读取undo文件再重启

centos mysql rpm re_centos7和centos6.5环境rpm方式安装mysql5.7和mysql5.6详解-程序员宅基地

文章浏览阅读79次。centos环境安装mysql5.7其实不建议安装mysql5.7 语法和配置可能和以前的版本区别较大,多坑,慎入1.yum方式安装(不推荐)a.安装mysql5.7 yum源centos6:wget dev.mysql.com/get/mysql-community-release-el6-5.noarch.rpmyum localinstall mysql-community-release-..._mysql-community-release-el6-5 noarch.rpm

跟我学 Java 8 新特性之 Stream 流(二)关键知识点_<a> a[] toarray(intfunction<a[]> generator);-程序员宅基地

文章浏览阅读390次。转载自 跟我学 Java 8 新特性之 Stream 流(二)关键知识点我们的第一篇文章,主要是通过一个Demo,让大家体验了一下使用流API的那种酣畅淋漓的感觉。如果你没有实践,我还是再次呼吁你动手敲一敲,自己实实在跑一遍上一篇的Demo。相信你的感受和理解也会随之加深的。继续探索流API的高级功能之前,我们先从接口级别全面了解一下流API,这个对于我们来说是至关重要的。接下来,我给..._ a[] toarray(intfunction generator);

最简单的基于DirectShow的示例:视频播放器自定义版_directshow demuxer-程序员宅基地

文章浏览阅读1.3w次,点赞10次,收藏11次。本文记录一个简单的基于DirectShow的自定义的视频播放器。这里所说的“自定义播放器”,实际上指的是自己在Filter Graph中手动逐个添加Filter,并且连接这些Filter的后运行的播放器。这么做相对于使用RenderFile()这种“智能”创建Filter Graph的方法来说要复杂不少,但是可以让我们更加了解DirectShow的体系。流程图最简单的基于DirectShow的自定_directshow demuxer

随便推点

Ubuntu64位编译Linux0.0.1所遇到的Bug(copy的,之后会总结)_boot/head.s: assembler messages:-程序员宅基地

文章浏览阅读4k次,点赞2次,收藏2次。编译是个很蛋疼的事情,本想把linux0.0.1在Ubuntu上跑起来然后就可以各模块的学习,没想各种问题。问题1:1 gas -c -o boot/head.o boot/head.s2 make: gas: Command not foundgas已过时,将所有Makfile里gas -> as具体解决方法1msed g_boot/head.s: assembler messages:

山东最新建筑施工焊工(建筑特种作业)机考题库及建筑焊工模拟试题_山东特种作业模拟考试焊工-程序员宅基地

文章浏览阅读125次。百分百题库提供特种工(焊工)考试试题、特种工(焊工)考试预测题、特种工(焊工)考试真题、特种工(焊工)证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。106.钢材在外力作用下产生塑性变形的能力称为(A)。 A.塑性 B.硬度 C.强度 D.断面收缩率107.(A)是金属材料抵抗永久变形和断裂的能力。 A.强度 B.冲击韧性 C.硬度 D.塑性 108.按照化学成分碳素钢中的低..._山东特种作业模拟考试焊工

mysql select语法_MySql SELECT 语法-程序员宅基地

文章浏览阅读508次。SELECT[ALL | DISTINCT | DISTINCTROW ][HIGH_PRIORITY][STRAIGHT_JOIN][SQL_SMALL_RESULT] [SQL_BIG_RESULT] [SQL_BUFFER_RESULT][SQL_CACHE | SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS]select_expr [, select_expr ......_mysql select语法

tensorflow:Not creating XLA devices, tf_xla_enable_xla_devices not set_i tensorflow/compiler/jit/xla_cpu_device.cc:41] no-程序员宅基地

文章浏览阅读2.5k次,点赞2次,收藏5次。运行代码出现I tensorflow/compiler/jit/xla_cpu_device.cc:41] Not creating XLA devices, tf_xla_enable_xla_devices not set以为是网上说的CUDA tensorflow-gpu 版本的问题可看后面,gpu还是正常运行了的I tensorflow/core/common_runtime/gpu/gpu_device.cc:1720] Found device 0 with properties:pc_i tensorflow/compiler/jit/xla_cpu_device.cc:41] not creating xla devices, tf

2021Java春招面试真题,java一年经验面试题_一年java工作经验的大学生面试题-程序员宅基地

文章浏览阅读160次。前言目前绝大部分的Java程序员都是处于增删改查的阶段,但是到了这个阶段后就应该考虑下一个层次的突破了,总不能做一辈子的crud吧…**以目前IT行业的发展趋势以及就业情况来看,**市场早已经不缺初级开发了,对于中高级开发人才倒是挺稀罕的,编程这一工作,如逆水行舟不进则退。技术不断更新,你可以设想一下,公司因为疫情的影响实在撑不下去了,你是不幸中枪的那一个,你之后的工作该怎么找?你的工作经验是否能匹配行业当前的招聘要求呢?当你的身体和思维已经形成了摸鱼划水的习惯,短期内迅速改变是非常困难的,你能做的只_一年java工作经验的大学生面试题

java 根据拼音查询汉字_java根据拼音搜索,但数据库为汉字的解决方案-程序员宅基地

文章浏览阅读1.1k次。[Java] 纯文本查看 复制代码**1.以下代码是一个文字转拼音的工具类**import org.springframework.stereotype.Component;import net.sourceforge.pinyin4j.PinyinHelper;import net.sourceforge.pinyin4j.format.HanyuPinyinOutputFormat;impor..._java根据拼音搜索汉字

推荐文章

热门文章

相关标签