[PAT解题报告] Forwards on Weibo
这个题我觉得也不难。给定微博上每个人的粉丝数，假设它发一条微博，所有粉丝都会转发，并且粉丝的粉丝也会转发……问L层之后有多少人转发，其实就是查询每个人的L级粉丝数。
如果A是B的粉丝，就连一条B到A的边，我们就有了一个有向图，原始问题变成了查询一个点距离不超过L的点有哪些了。
查询有多个，显然可以根据每个查询bfs
L层……我采用了最暴力的做法，先用n^3的floyd算出任意两点间的最短路，对每个查询，枚举所有点，把距离不超过L的都输出就好了。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int f[1024][1024];
void better(int &x,int y) {
if ((x < 0) || (x > y)) {
x = y;
}
}
int main() {
int n,m;
memset(f,0xff,sizeof(f));
scanf("%d%d",&n,&m);
for (int i = 1; i <= n; ++i) {
int j;
for (scanf("%d",&j);j;--j) {
int x;
scanf("%d",&x);
f[x][i] = 1;
}
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
if (f[i][k] >= 0) {
for (int j = 1; j <= n; ++j) {
if (f[k][j] >= 0) {
better(f[i][j],f[i][k] + f[k][j]);
}
}
}
}
}
int x;
for (scanf("%d",&x);x;--x) {
int y;
scanf("%d",&y);
int z = 0;
for (int i = 1; i <= n; ++i) {
if ((i != y) && (f[y][i] >= 0) && (f[y][i] <= m)) {
++z;
}
}
printf("%d\n",z);
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1076
查看12道真题和解析
