PAT 解题报告 1076. Forwards on Weibo (30)

1076. Forwards on Weibo 题目描述:

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.

就是求微博的最大转发数量, 给出某张微博的社交网络图, 然后求其中某个用户微博的最大可能的转发数量, 每个follower转发一次, 统计L层非直接关注关系.

1076. Forwards on Weibo 算法分析:

这个题目算法就是BFS, 就是题目貌似有点难读懂, assuming that only L levels of indirect followers are counted. 这句话的正确理解是统计到距离起始点L层的那层follower即可, 也就是说比如2<—3<—4<—5, 那么3是2的直接follower, 4是第二层的简介follower, 5是第三层的间接(非直接)follower, 如果输入的L是2, 那么我们的BFS统计到4这一层就好了. L是3就统计到5这一层. 总结算法就是利用BFS, 统计到L层的follower个数. 可以AC的代码如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

int bfs(int iStart, const std::vector< std::vector<int> >& vecGraph, int N, int L)
{
	int iCount = 0;
	std::vector<int> vecDistance(N, -1);
	std::queue<int>	  q;

	q.push(iStart);
	vecDistance[iStart] = 0;

	while(!q.empty()) {
		int iCurrentNode = q.front(); q.pop();
		if(vecDistance[iCurrentNode] >= L)
			break;
		for(auto it = vecGraph[iCurrentNode].begin();
			it != vecGraph[iCurrentNode].end(); ++it) {
				if(-1 == vecDistance[*it]) {
					q.push(*it);
					vecDistance[*it] = vecDistance[iCurrentNode] + 1;
					++iCount;
				}
		}
	}
	return iCount;
}

int main()
{
	int N, L;
	std::vector<std::vector<int>> vecGraph;

	scanf("%d %D", &N, &L);
	vecGraph.resize(N);
	int iNumForwardLink;
	int iNode;
	for(int i = 0; i < N; ++i) {
		scanf("%d", &iNumForwardLink);
		for(int j = 0; j < iNumForwardLink; ++j) {
			scanf("%d", &iNode);
			vecGraph[iNode - 1].push_back(i);
		}
	}
	int iNumQuery;
	scanf("%d", &iNumQuery);
	for(int i = 0; i < iNumQuery; ++i) {
		scanf("%d", &iNode);
		printf("%d\n", bfs(iNode - 1, vecGraph, N, L));
	}
	return 0;
}

1076. Forwards on Weibo 注意点:

题目意思容易误解,  assuming that only L levels of indirect followers are counted的意思是统计到L层为止, 直接follower算第一层也要统计进最后的结果.

Written on March 7, 2014