题目粗心:
在微博中,每个用户都可能被若干其余用户关注。而当该用户公布一条音讯时,关注他的人就能够看到这条信息并且抉择是否转发它,且转发的音讯也能够被关注他的人再次转发,然而同一用户最多转发该信息一次(信息的最后发布者不能转发该音讯),当初给出N个用户的关注状况以及一个转发层数下限L,并给出最后公布音讯的用户编号,求在转发层数下限内音讯最多会被多少用户转发
算法思路:
首先得了解题意
assuming that only L levels of indirect followers are counted.
这里的$indirect$ $followers$指的是除了发布者以外的关注他的人,而不是在所有关注者中除了第一个关注者之外的人
calculate the maximum potential amount of forwards for any specific user
这句话指的是计算L层内的所有不同的人有多少个,$potential$ $ amount$就是可能转发的意思,其实就是以发布者为核心的L层内的总人数,对于人A有关注A的人B存在,那么A公布的微博B是能够看的到的,那么就存在一条微博传递门路$A->B$,对于输出中$user[i]$和$userlist[i]$实际上是$user[i]$关注了$userlist[i]$,所以有一条$userlist[i]->user[i]$的微博传递门路。
在了解题意后很分明的晓得咱们要求的是在发布者为核心流传L层内的所有人数,很天然就联想到广度优先遍历的办法求解此题。为了不便的记录每一个节点的层数从而统计L层内的人数,咱们建设构造体Node将人员的编号和层数进行绑定,而后在广度优先遍历的时候,每次出队的时候,只有出队节点的层数大于L,间接退出循环,否则就统计除了自己的转发人数。
留神点:
- 1、应用DFS最初一个测试点会超时。
- 2、每一个人只能转发一次,须要去重,能够应用$unordered$_$set$解决,这里应用了入队标记数组。
- 3、每次查问须要初始化$visited$
- 4、存储数组大小得开到1001以上否则最初一组测试点呈现运行时谬误。
提交后果:
AC代码:
#include <cstdio>#include <vector>#include <queue>#include <cstring>using namespace std;struct Node{ int index; int level;};int N,L;//总人数,层数vector<int> G[1001];// 设置为1000会导致测试点4运行时谬误bool visited[1001];// 入队标记数组void BFS(int start){ queue<Node> q; q.push(Node{start,0}); int count = 0;// 统计L层内的人数 visited[start] = true; while(!q.empty()){ Node top = q.front(); q.pop(); if(top.level>L){ break; } else { // 不统计本人 if(top.index!=start) ++count; for(int i=0;i<G[top.index].size();++i){ int next = G[top.index][i]; if(!visited[next]){ visited[next] = true; q.push(Node{next,top.level+1}); } } } } printf("%d\n",count);}int main(){ scanf("%d %d",&N,&L); int num,followed; for (int i = 1; i <= N; ++i) { scanf("%d",&num); for (int j = 0; j < num; ++j) { scanf("%d",&followed); G[followed].push_back(i); } } int K,user; scanf("%d",&K); // K个查问 for(int i=0;i<K;++i){ scanf("%d",&user); memset(visited,0, sizeof(visited)); BFS(user); } return 0;}