题意:linji的仓鼠丢了,他要找回仓鼠,他在房间0放了一块奶酪,按照抓鼠手册所说,这块奶酪可以吸引距离它D的仓鼠,但是仓鼠还是没有出现,现在给出一张关系图,表示各个房间的关系,相邻房间距离为1,而且图中没有回路,每个房间都是联通的,求仓鼠可能出现的房间的数量。
很容易的dfs,50000个房间数据量比较大,用数组难以保存,于是用vector储存关系表。遍历过去,遍历过几个房间,那剩下的就是仓鼠可能出现的房间数了。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: 2.cpp
* Create Date: 2013-09-08 13:52:18
* Descripton: dfs
*/
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define mc(a) memset(a, 0, sizeof(a))
const int MAXN = 1e5 + 1;
vector<int> v[MAXN];
int n, d, cnt;
bool vis[MAXN];
void dfs(int p, int e) {
if (e > d) return;
vis[p] = 1;
cnt++;
int len = v[p].size();
rep(i, len)
if (!vis[v[p][i]])
dfs(v[p][i], e + 1);
}
int main() {
int t, a, b;
scanf("%d", &t);
while (t--) {
rep(i, n) v[i].clear();
mc(vis);
cnt = 0;
scanf("%d%d", &n, &d);
rep(i, n - 1) {
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(0, 0);
printf("%d\n", n - cnt);
}
return 0;
}
分享到:
相关推荐
HDU2013暑期多校联合训练第一场0723-解题报告和标程
在webDIY 和DIY中总结的专题训练
离线OJ题库(HDU ZJU等,部分有答案),需联网。
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
hdu动态规划算法集锦
搜索 dfs 解题代码 hdu1241
HDU的一题........HDU DP动态规
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU 动态规划(46道题目
100道 acm C语言 hdu 解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
这是HDU acm 其中一部分题的代码,后续代码会继续上传。
hdu1001解题报告
hdu 1574 passed sorce
关于hdu的动态规划的题目,包括一些水题,还有一些经典的动态规划题目。