PAT1076 Forwards on Weibo BFS+图

布满荆棘的人生 2023-02-25 07:10 167阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70][]

思路：有向图的bfs搜索，注意题目的逻辑关系，即谁可以转发谁，因为数据量比较大，邻接矩阵存储然后遍历每个点的话代价太大，不过题目时间给了三秒....

如果时间要求高的话，应改用邻接表存储，直接判断一下当前的人有多少次被关注就行，不用一一判别，省很多时间。注意每次查询之前需要更新inqueue数组，所有点设置为未访问

#include<iostream>
    #include<queue> 
    using namespace std;
    struct node{
        int data,layer;
    };
    int follow[1005][1005]={0};//follow[a][b]表示b关注a
    bool inqueue[1005]={false};
    int n,l;
    void bfs(int now)
    {
        queue<node> q;
        int num=0;
        node it={now,0};
        q.push(it);
        inqueue[now]=true;
        while(!q.empty())
        {
            node f=q.front();
            q.pop();
            for(int i=1;i<=n;i++)//最暴力法，还是过了，时间要求真低
            {
                if(follow[f.data][i]==1&&inqueue[i]==false&&f.layer<l){
    			inqueue[i]=true;num++;q.push({i,f.layer+1});}
            }
        }
        cout<<num<<endl;
    }
    int main()
    {
        cin>>n>>l;
        int k,temp;
        for(int i=1;i<=n;i++)
        {
            cin>>k;
            while(k--)
            {
                cin>>temp;
                follow[temp][i]=1;
            }
        }
        cin>>k;
        while(k--)
        {
            cin>>temp;
            for(int i=0;i<1005;i++)inqueue[i]=false;
            bfs(temp);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230209/857dc27b54e04aa5a3107a3f29a77503.png