1076. Forwards on Weibo (30)-PAT甲级真题(图的遍历bfs)

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 are 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

题目大意:

给出每个用户关注的人的id,和转发最多的层数,求一个id发了条微博最多会有多少个人转发

分析:

带层数的广度优先,因为一个用户只能转发一次,所以用inq判断当前结点是否入队过了,如果入队过了就不能重复入队(重复转发消息),inq 邻接表v 都可以使用int只存储id,queue的数据类型必须为node,同时保存它的id和layer层数,控制不超过L层~

原文链接:https://blog.csdn.net/liuchuo/article/details/52292939

本文来自博客园,作者:勇往直前的力量,转载请注明原文链接:https://www.cnblogs.com/moonlight1999/p/15873373.html

推荐这些文章:

洛谷马的遍历

题目链接:https://www.luogu.com.cn/problem/P1443
马走日字象走田,究竟怎么走呢?

画画图就明白啦,
除此之外,这个题就是一道稍微变形的bfs题目,需要注意的是,左对齐输出一定要有,否则你即使是运行结果对了也怎么都是WA,别问,说多了都是泪

1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m,sx,sy;
4 int dis[410][410];
5 int dir[8][2]={
6 {-2,-1},
7 {-2,1},
8 {-1,...

PAT(甲级)2019年秋季考试练习

1160 Forever (20 分)
"Forever number" is a positive integer A with K digits, satisfying the following constrains:
the sum of all the digits of A is m;
the sum of all the digits of A+1 is n; and
the greatest common divisor of m and n is a prime number which is greater than 2.
Now you are supposed to ...

PAT 甲级 1064 Complete Binary Search Tree解题思路(全网最清晰之一)

网上看了很多关于这题的解答,基本上都没讲的太清楚,关于解题思路很多都是一笔带过,然后给出大段的代码,这种解题文章没意思。
本文只讲解题思路,不给出代码,但求尽量把解题思路讲清晰。
做本题所必需的前置知识条件

二叉排序树的中序遍历序列是一个递增序列,这个是做这道题必须知道的前置知识。

二叉树的中序遍历方式,是本题所需的第二个知识,最简单的方法就是用递归的方式。注意,这里的中序遍历方式是对所有二叉树都有用的,而并不是单单针对二叉排序树,后面两个知识也同样是针对所有二叉树的。

完全二叉树的存储方式,可以直接用一维数组存储,这是做本题所需的第三个知识。其中,假设父结点在数组中的编号为i,...

蓝桥杯真题 迷宫

考点
1、BFS求最短路径的长度
2、枚举求出路径走法(注意枚举过程中要按照字典序最小的方案来求)
题目描述
下图给出了一个迷宫的平面图,其中标记为1 的为障碍,标记为0 的为可 以通行的地方。
010000000100001001110000
迷宫的入口为左上角,出口为右下角,在迷宫中,只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫,从入口开始,可以按DRRURRDDDR 的顺序通过迷宫, 一共10 步。其中D、U、L、R 分别表示向下、向上、向左、向右走。
对于下面这个更复杂的迷宫(30 行50 列),请找出一种通过迷宫的方式, 其使用的步数最少,在步数最少的前...

1151 LCA in a Binary Tree (30 分)(树的遍历,LCA算法)

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.
Given any two nodes in a binary tree, you are supposed to find their LCA.
Input Specification:
Each input file contains one test case. For each case, the first line gives two po...

PAT甲级1164 Good in C

这是我甲级写的第一题,感觉是比较麻烦的一道模拟题。输出格式卡了老久了(太弱了属于是,写这么长时间已经算失败了
思路不难想,先把题目给的26个字母存下来,然后处理字符串再输出就可以了,细节扣的比较多
下附20分代码:
#include<bits/stdc++.h>
using namespace std;

char arr[100][7][5];

void printc(string s){
for(int i=0;i<7;i++){
for(int x=0;x<s.size();x++){
char c = s[x]...

数据结构-图的遍历——BFS广度优先搜索

题目链接:https://www.dotcpp.com/oj/problem1703.html?sid=7509237&lang=1#editor
板子题,需要注意的是利用邻接矩阵存图,但是这样就变成了纯bfs模板,只要判断是否是走过并且这个点是否能走就可以了,
而对于图来说,尤其是利用邻接矩阵存图,0代表的是这条边不是图的边,1代表这条边是图的边,
而对于网图来讲,Gij代表的是这个图的边,并且是权值,而0或者是INF(无穷大)则代表不是图的边。
然后这个题就可以用bfs了:
Talk is cheap. Show me the code.

1 #include<bits...

求助:文件夹下面文件灰常多,怎么遍历哟?

问题
想遍历一个文件夹下面的文件。
大概有30个G的txt文档。

有什么好的方法,最好的依次的读哟。

最佳回答
得到文件夹信息、一个循环、就可以啊

...

pat甲级打卡-1004 Counting Leaves (测试点3未通过)

1004 Counting Leaves (30 分)
https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184
测试点3一直过不去不清楚为什么,检查了很久没检查出来,不过bfs记录层数还是很重要的。好题一道
#include<bits/stdc++.h>
using namespace std;
const int N=101;
//建树
int n,m;
int ne[N],idx,e[N],h[N];
int depth[N];
int layer[N]; //存每层的叶节点数...

2020 PAT秋季甲级考试(91分)-记

2020-9-5 刚考完PAT
最后半小时手机居然关机断网了!!!
题目描述可以参考2020年PAT秋原题
第一题(奶牛题)
好坑,我想的是找出单调序列,从小到大依次赋值,序列最大的点先放着,之后根据两边的值确定每个最大点处的值。最后一个点wa(-3分)

code1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[10005];
int main()
{
int N; cin>>N;
int a[N+3];
for(int i=1;i<=...

文章标题:1076. Forwards on Weibo (30)-PAT甲级真题(图的遍历bfs)
文章链接:https://www.dianjilingqu.com/50968.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>