PAT甲级1076Forwards on Weibo

Posted on | | Visitors:
Words count in article: 419 字 | Reading time ≈ 2 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736

题解

题目要求

  • 给定一个社交网络，请计算某用户的最大转发量（只计算L层间接关注者，假设一条微博，每个人只能转发一次）。
  • 输入
    • N：正整数，不超过1000，用户的数量，索引为[1,N]
    • L：正整数，不超过6，需要计算的间接关注者的层数
    • N个用户分别关注了哪些用户：每个用户关注的用户列表
    • K：正整数，要查询的用户的数量
    • K个要查询的用户：
  • 输出

解题思路

  • 需要判断层次的BFS：通过类来保存每个结点的层次即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Problem: PAT Advanced 1076
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736
// Tags: 图 BFS

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1001;
int n, l;
bool visit[MAXN];
vector<int> followers[MAXN];

struct User{
    int id,layer;
};

int bfs(int tempID){
    queue<User> users;
    users.push({tempID, 0});
    visit[tempID] = true;
    int ret = 0;
    while (!users.empty()){
        User u = users.front();
        users.pop();
        for (auto it = followers[u.id].begin(); it != followers[u.id].end(); it++){
            if (!visit[*it] && u.layer < l){
                visit[*it] = true;
                users.push({*it, u.layer + 1});
                ret++;
            }
        }
    }
    return ret;
}

int main()
{
    scanf("%d %d", &n, &l);
    int tempUser, m;
    for(int i = 1; i <= n; i++){
        scanf("%d", &m);
        for(int j = 0; j < m; j++){
            scanf("%d", &tempUser);
            followers[tempUser].push_back(i);
        }
    }

    int k;
    scanf("%d", &k);
    while(k--){
        scanf("%d", &tempUser);
        fill(visit, visit + MAXN, false);
        printf("%d\n", bfs(tempUser));
    }
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!