Java教程

PAT1076

本文主要是介绍PAT1076,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

思路:该问题求最多转发层数内最多的转发人数,实际上就是从所要求的点进行BFS,然后计算限制层数内的节点数。
代码如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <string.h>

using namespace std;


/*一个节点*/
struct node {
	int id;		//节点编号
	int level;	//BFS的层数
	node(int x,int y):id(x),level(y){}
};

#define MAX 1010
//总人数
int N = 0;
//转发层数
int L = 0;
//被查询的人的数量
int K = 0;
//邻接矩阵,节点编号从1开始
vector<node> adj[MAX];
//节点是否进入过队列
bool inq[MAX] = { false };


/*读部分输入*/
void input() {
	cin >> N >> L;
	for (int i = 1; i <= N; i++) {
		//节点的前驱数n
		int n;
		cin >> n;
		for (int j = 0; j < n; j++) {
			//前驱节点的编号x
			int x;
			cin >> x;
			adj[x].push_back(node(i,0));
		}
	}
}



/*对指定编号的节点,求最大转发数*/
int cal(int id) {
	//计数器
	int cnt = -1;	

	//对id进行BFS
	queue<node> q;
	q.push(node(id,0));
	inq[id] = true;
	while (!q.empty()) {
		int cid = q.front().id;	//当前栈顶id
		node front = q.front();
		q.pop();
		
		//判断是否超过层数
		if ( front.level> L)
			break;

		cnt++;

		for (int i = 0; i < adj[cid].size(); i++) {
			int v = adj[cid][i].id;
			if (!inq[v]) {							
				inq[v] = true;
				q.push(node(v, front.level + 1));
			}
		}
	}

	return cnt;
}


int main(void) {
	input();
	
	cin >> K;
	for (int i = 0; i < K; i++) {
		int j;		//当前要计算的节点的编号
		cin >> j;
		cout<<cal(j)<<endl;

		//重置inq数组
		memset(&inq, false, MAX);
	}
	
}




这里要注意每对一个待求的点进行BFS前,都要重置inq数组。
另外,邻接表中的元素其实不应该是node类型,使用int型即可,这是代码的一个问题。

这篇关于PAT1076的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!