hdu 4707 Pet（DFS && 邻接表）
2024-08-28 01:03:08
Pet
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1809 Accepted Submission(s): 874
Problem Description
One day, Lin Ji wake up in the morning and found that his pethamster escaped. He searched in the room but didn’t find the hamster. He tried to use some cheese to trap the hamster. He put the cheese trap in his room and waited for
three days. Nothing but cockroaches was caught. He got the map of the school and foundthat there is no cyclic path and every location in the school can be reached from his room. The trap’s manual mention that the pet will always come back if it still in somewhere
nearer than distance D. Your task is to help Lin Ji to find out how many possible locations the hamster may found given the map of the school. Assume that the hamster is still hiding in somewhere in the school and distance between each adjacent locations is
always one distance unit.
three days. Nothing but cockroaches was caught. He got the map of the school and foundthat there is no cyclic path and every location in the school can be reached from his room. The trap’s manual mention that the pet will always come back if it still in somewhere
nearer than distance D. Your task is to help Lin Ji to find out how many possible locations the hamster may found given the map of the school. Assume that the hamster is still hiding in somewhere in the school and distance between each adjacent locations is
always one distance unit.
Input
The input contains multiple test cases. Thefirst line is a positive integer T (0<T<=10), the number of test cases. For each test cases, the first line has two positive integer N (0<N<=100000) and D(0<D<N), separated by a single space.
N is the number of locations in the school and D is the affective distance of the trap. The following N-1lines descripts the map, each has two integer x and y(0<=x,y<N), separated by a single space, meaning that x and y is adjacent in the map. Lin Ji’s room
is always at location 0.
N is the number of locations in the school and D is the affective distance of the trap. The following N-1lines descripts the map, each has two integer x and y(0<=x,y<N), separated by a single space, meaning that x and y is adjacent in the map. Lin Ji’s room
is always at location 0.
Output
For each test case, outputin a single line the number of possible locations in the school the hamster may be found.
Sample Input
1
10 2
0 1
0 2
0 3
1 4
1 5
2 6
3 7
4 8
6 9
Sample Output
2
Source
求全部房子建一颗树，到根节点距离大于 D的节点的个数
DFS。邻接表存储，，。第一次用邻接表。对于菜鸟的我，
第一次接触还真不好理解。我把我理解半天的邻接表存储的都凝视了
希望对小伙伴们理解有帮助，，
#include<stdio.h>
#include<string.h>
#define M 100100
struct node{
int to,next,w;//w为边权值
}edge[M];
int head[M];
int cnt,n,m,ans;
void add(int x,int y){//邻接表是对每一条边进行编号，从0開始。
edge[cnt].to=y;//edg[cnt].to表示编号为cnt的那条边的终点
edge[cnt].next=head[x];//edge[cnt].next表示和cnt这条边同起点的下一条边的编号
head[x]=cnt++;//head[i]的意思是以i为起点的第一条边的编号，（ 事实上就是以i为起点最后输入的那条边的编号，就是逆序第一条边的编号）
}
void dfs(int x,int w){
if(head[x]==-1)
return;
for(int i=head[x]; i!=-1 ;i=edge[i].next){//从以x为起点的最后一个输入的边開始遍历
//i=edge[i].next表示和上一条边同起点的下一条边的编号，依次遍历
int to=edge[i].to;
edge[i].w=w+1;
if(edge[i].w > m)
ans++;
dfs(to,edge[i].w);
}
}
int main(){
int t,i,a,b;
scanf("%d",&t);
while(t--){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
cnt=0;
for(i=0;i<n-1;i++){
scanf("%d%d",&a,&b);
add(a,b);
}
ans=0;
dfs(0,0);
printf("%d\n",ans);
}
return 0;
}
最新文章
- PHP函数整理（一）
- 大熊君JavaScript插件化开发------（实战篇之DXJ UI ------ ProcessBar）
- 使用File类列出指定位置的文件信息，包含该路径子目录下的文件信息
- oracle学习笔记
- job
- jQuery带遮罩层弹窗实现（附源码）
- linux下安装mysql-community后起不来
- BZOJ 1093: [ZJOI2007]最大半连通子图( tarjan + dp )
- 面向对象三大特征之继承（extends）——Java笔记（六）
- 学习ASP.NET MVC(十一)——分页
- javascript+HTMl5游戏下载，开发一个都能月薪上万！舅服你
- d3根据数据绘制不同的形状
- Fedora 23建立wifi热点（Android手机可用）
- 细说@Html.ActionLink()的用法（转）
- 【转】Mybatis源码解读-设计模式总结
- vscode跳转到函数定义处
- NEST - Elasticsearch 的高级客户端
- MT【38】与砝码有关的两个题
- Apache目录结构解释
- NodeJS的url验证库模块url-valid