[数据结构与算法]1076 Forwards on Weibo

1076 Forwards on Weibo

题意描述

给出图结构 求某个节点发出信息在层数限制下能够转发的最多人数

输入输出格式

数据规模

节点数 <= 1e3

算法设计

像这种模型最适合使用BFS来求解了。BFS搜索的过程更像是水面波纹扩散，一圈一圈的，而且第一次到达某个节点时，其扩散次数一定是最少的，由此便有BFS最短路模型，比如 一次跳两个或三格 问到达目的地要跳几次 跳的过程好比扩散搜索的过程，结构便是扩散的次数，也是就扩散的层数 还有 八数码问题 问移动几次能够到达目表状态 还有 迷宫搜索 问移动几步能够到达出口 这些问题都可以使用BFS来求解
它们都具有一个很重要的特征 扩散一次 答案加一个定值 如果有些搜索答案加一 有些加二 即带权值的搜索 这就不再适合使用BFS最短路模型了

c++11代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg maxn = 1e3 + 10;
vector<vector<gg>>adj(maxn);
vector<bool>inq(maxn);
gg BFS(gg x, gg level){     //  这种步数模型最好使用BFS进行搜索 特点是 每扩散一次，结果 +1 BFS最短路 
    queue<array<gg,2>>q;
    q.push({x,0});
    inq[x] = true;
    gg num = 0;
    while(not q.empty()){
        auto top = q.front();
        q.pop();
        for(auto i : adj[top[0]]) {
            if(not inq[i]){
                inq[i] = true;
                if(top[1] + 1 <= level){
                    num++;   //  入队才转发
                    q.push({i,top[1] + 1});
                }
            }
        }
    }
    return num;
}
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0);
   gg n,level,user,follow,k;
   cin>>n>>level;
   for(gg i =1;i<=n;i++){
       cin>>user;
       while(user--){
           cin>>follow;
           adj[follow].push_back(i);
       }
   }
   cin>>k;
   while(k--){
       fill(inq.begin(),inq.end(),false);
       cin>>user;
       cout<<BFS(user,level)<<"\n";
   }
   return 0;
}

题目链接