当前位置：首页 > news >正文

PAT 甲级 1076 Forwards on Weibo（30）

news 2024/11/6 23:28:56

🟠 题目大意
🟡 输入输出
🔵 深度优先搜索（dfs）
🟢 宽度优先搜索（bfs）
🟤 总结和提炼

原题链接

在这里插入图片描述

🟠 题目大意

分析题干，每个人有自己的推文和关注者，关注者可以转发被关注者的推文，限定最多转发L次，要求计算出某作者推文被阅读的最多人数。

🟡 输入输出

题目输入两个整数n和l，分别代表user的人数和最大转发层数。
接下来n行，每行第一个数字代表索引为i的作者关注的人数M[i]，随后索引为i的作者关注的M[i]个user。最后一行的第一个数是要测试的k个人数，随后是k个user，计算给定UserID被浏览的最多人数。
将给定的userID推文被浏览的最多人数打印，每个输出占一行。

通过分析题目大意，“关注者可以转发被关注者的推文，限定最多转发L次”，可以联想到使用搜索去实现这个思路。关注者可以转发被关注者的推文——本质上是一种递归或者循环，而最大转发层数L则是递归或循环的结束条件。

思考到这里，第一个涌入脑海的方法就是dfs👇🏽

🔵 深度优先搜索（dfs）

思路很简单
（1）从给定的原UserID开始，遍历关注这个UserID的所有关注者

int sum = list[id].size();//关注当前id作者的人数for (int i = 0; i < sum; i++){}

（2）如果当前关注者没有关注原UserID，计入总人数

int fid = list[id][i];//关注者if (!vis[fid])//如果关注者没访问过原作者推文{scnt++;vis[fid]=true;}

（3）设置循环条件，层数<=L，传入当前关注者作为一次循环的被关注者，层数+1

if(lever+1<=l) dfs(fid, lever + 1);

到这里，我们已经把搜索的基本流程解决了，下面是完整代码。

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 1010;
const int MAXM = 110;
vector<vector<int>>list;//list[i][j]说明i作者有j跟随着
bool vis[MAXN];//判断当前id的人是否访问过原作者
int n, l;
int scnt = 0;//记录访问原作者推文的人数void dfs(int id,int lever)
{int sum = list[id].size();//关注当前id作者的人数for (int i = 0; i < sum; i++){int fid = list[id][i];//关注者if (!vis[fid])//如果关注者没访问过原作者推文{scnt++;vis[fid]=true;}if(lever+1<=l) dfs(fid, lever + 1);//无论是否关注都不影响继续转发，限制的唯一条件是转发层数l}
}int main()
{cin >> n >> l;list.resize(n + 1);for (int i = 1; i <= n; i++){int s;cin >> s;for (int j = 1; j <= s; j++){int x; cin >> x;list[x].push_back(i);//索引为i的id有关注者x，因此是x被i关注，}}//查询idint k; cin >> k;while (k--){memset(vis, false, sizeof(vis));scnt = 0;int id; cin >> id;vis[id] = true;//自己不算dfs(id,1);//作者id 和 转发层数cout << scnt << endl;}return 0;
}

观察测评结果，可以看到只通过了90%样例
原因可能是发生了栈溢出（stackoverflow），即不断的（递归）调用某个函数。

要解决这个问题很简单

☑️dfs是递归搜索，那么我们采用非递归搜索就可以了。

因此，第二个方法就很容易想到了👇🏽

🟢 宽度优先搜索（bfs）

思路和深搜相似
（1）创建队列并将目标ID推入队列

queue<Node>q;//创建队列q
node.id = id;
node.lever = 1;
q.push(node);//推入目标ID

（2）队列非空时取出队头（当前循环的被关注者）

while (!q.empty())//队列非空时继续循环
{Node newnode = q.front();//取出队头q.pop();}

（3）遍历当前ID的所有关注者，符合条件则push进队列

int lever = newnode.lever;int sum = list[newnode.id].size();
int nid = newnode.id;for (int i = 0; i < sum; i++)//遍历当前ID所有关注者
{int follower = list[nid][i];if (!vis[follower])//如果没有当前关注者没有浏览过原作者ID推文{scnt++;vis[follower] = true;}if (lever <= l)//如果转发层数不大于L{node.id = follower;node.lever = lever + 1;q.push(node);}
}

（4）重复步骤(2)(3)直到队列为空

以下是完整代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 1001;
vector<int>list[MAXN];//list[i][j]说明i作者有j跟随着
int n, l;
int scnt = 0;//记录访问原作者推文的人数struct Node
{int id;int lever;
}node;void bfs(int id)
{bool vis[MAXN] = { false };//判断当前id的人是否访问过原作者vis[id] = true;queue<Node>q;node.id = id;node.lever = 1;q.push(node);while (!q.empty()){Node newnode = q.front();q.pop();int lever = newnode.lever;int sum = list[newnode.id].size();int nid = newnode.id;for (int i = 0; i < sum; i++){int follower = list[nid][i];if (!vis[follower])//如果没有当前关注者没有浏览过原作者ID推文{scnt++;vis[follower] = true;}if (lever <= l)//如果转发层数不大于L{node.id = follower;node.lever = lever + 1;q.push(node);}}}
}int main()
{cin >> n >> l;for (int i = 1; i <= n; i++){int s;cin >> s;for (int j = 1; j <= s; j++){int x; cin >> x;list[x].push_back(i);//索引为i的id有关注者x，因此是x被i关注，}}//查询idint k; cin >> k;while (k--){scnt = 0;int id; cin >> id;bfs(id);cout << scnt << endl;}return 0;
}

观察测试结果，可以发现出现了内存超限，即堆内存溢出
要如何解决内存超限问题呢？

☑️对于搜索算法，最常见的优化方式就是——剪枝

剪枝是什么？

☑️在搜索算法中，剪枝是一种优化技术，用于提高搜索效率，特别是在解决决策问题时。剪枝的基本思想是避免搜索那些不会带来更好结果的路径，从而减少计算量和提高搜索速度（即通过减少搜索不必要的情况提高推理速度，降低存储需求）

回到代码中，我们要如何使用剪枝优化呢？

思考一下，在循环过程中，有哪些情况是不会带来更好结果的呢，有没有重复搜索的地方呢？

☑️可以发现，如果当前被循环的关注者在本次循环之前已经浏览过原ID的推文，说明这个关注者在本次循环前已经加入队列，那么很明显，如果继续循环这个关注者，它就被重复搜索了。

因此我们只需要给推入队列加个条件就可以了——如果转发层数不大于L且当前关注者没有访问过原ID推文

//剪枝前：
//if (!vis[follower])//如果没有当前关注者没有浏览过原作者ID推文
//{
//	scnt++;
//	vis[follower] = true;
//}
//if (lever < l)//如果转发层数小于l
//{
//	node.id = follower;
//	node.lever = lever + 1;
//	q.push(node);
//}
//剪枝后：
if (!vis[follower]&&lever<=l)//如果当前关注者没有访问过原ID推文且转发层数不大于l
{scnt++;vis[follower] = true;node.id = follower;node.lever = lever + 1;q.push(node);
}

可以看到修改后的代码通过了全部测试样例

在这里插入图片描述

AC代码

//bfs（pta平台能通过100%样例）
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 1001;
vector<int>list[MAXN];//list[i][j]说明i作者有j跟随着
int n, l;
int scnt = 0;//记录访问原作者推文的人数struct Node
{int id;int lever;
}node;void bfs(int id)
{bool vis[MAXN] = { false };//判断当前id的人是否访问过原作者vis[id] = true;queue<Node>q;node.id = id;node.lever = 1;q.push(node);while (!q.empty()){Node newnode = q.front();q.pop();int lever = newnode.lever;int sum = list[newnode.id].size();int nid = newnode.id;for (int i = 0; i < sum; i++){int follower = list[nid][i];//剪枝后：if (!vis[follower]&&lever<=l)//如果当前关注者没有访问过原ID推文且转发层数不大于l{scnt++;vis[follower] = true;node.id = follower;node.lever = lever + 1;q.push(node);}}}
}int main()
{cin >> n >> l;for (int i = 1; i <= n; i++){int s;cin >> s;for (int j = 1; j <= s; j++){int x; cin >> x;list[x].push_back(i);//索引为i的id有关注者x，因此是x被i关注，}}//查询idint k; cin >> k;while (k--){scnt = 0;int id; cin >> id;bfs(id);cout << scnt << endl;}return 0;
}

Q：为什么剪枝前的条件是lever<l，剪枝后就变成lever<=l？
这是因为有两个判断
（1）判断推入队列
（2）判断当前关注者是否浏览原ID推文

剪枝前两个判断是分开的，当lever==l时，第一个判断不成立，但是第二个判断任然成立，因此lever==l正好是最后一次转发，因此可以被浏览。

这里使用嵌套if可以进一步优化，这样就不会把lever>l的情况推入队列了。

if (!vis[follower])//如果当前关注者没有访问过原ID推文
{scnt++;vis[follower] = true;if (lever < l)//且转发层数小于l{node.id = follower;node.lever = lever + 1;q.push(node);}
}