【DFS+堆的二叉树结构】15轻院校赛-J-堆

【题目链接：J-堆】

1734: 堆

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 239 Solved: 113

Submit Status Web Board

Description

Input

Output

Sample Input

10 5 3

1 2

1 3

1 2 3 4 5

3 1

2 1

2 4

2 5

Sample Output

Yes

【思路】

　　堆：堆最重要的性质就是儿子的值一定不小于父亲的值。除此之外，树的节点是按从上到下、从左到右的顺序紧凑排列的。

　　　　本题的堆是一种叫做二叉堆的数据结构。

　　　　《挑战程序设计》 P71

　　对于这题，首先要模拟出二叉树的结构，根据题意通过value[]保存每个节点的权值（值）

　　　　　　　再将每两节点之间是否有边连接，保存为tree[][],通过输入的两节点a,b，即保存tree[a][b] = 1

　　　　　　　1. 在接下来的深搜中，只需搜索tree[][] == 1的节点

　　　　　　　2. 同时，在搜索中还需要满足最小堆（堆）的性质，即value[节点] <= value[子节点]

　　　　　　　若符合以上1.2两个条件，则继续向深处（子节点）搜索

　　　　　　　　　　即dfs（深度优先搜索）的性质：列举出所有可能，每种可能搜索至，直到边界，或不符合条件为止。（不撞南墙不回头）

　　　　　　　依旧，还需要一个数组来保存，当前的节点是否被搜索过，即see[] = 1

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std; 
 4 #define Max(a,b) (a > b ? a : b)
 5 #define Min(a,b) (a < b ? a : b)
 6 const int MAXN = 410;
 7 int value[MAXN],tree[MAXN][MAXN],see[MAXN],ac,m;
 8 void dfs(int k){
 9     see[k] = 1; //表示已搜过 
10     for(int j = 1;j <= m;j++){
11         if(tree[k][j] && !see[j]){   //没搜索过，并且两节点间存在边 
12             if(value[k] <= value[j]) //当前节点权值小于或等于它的子节点权值 
13                 dfs(j);
14             else
15                 ac = 1;
16         }
17     }
18 }
19 int main(){
20     int n;
21     scanf("%d",&n);
22     while(n--){
23         memset(tree,0,sizeof(tree));
24         memset(see,0,sizeof(see));
25         int i;        
26         cin >> m;
27         for(i = 1;i <= m;i++){            
28             cin >> value[i];
29         }
30         for(i = 1;i < m;i++){
31             int a,b;        
32             cin >> a >> b;
33             //tree[a][b] = 1; 如果这样，那么：
34 //            1 2   与   1 2 
35 //            1 4        1 4
36 //            4 3        3 4
37 //            4 5        4 5
38 //            结果为前者是Yes 后者为 No 
39             //应为：
40             tree[a][b] = 1;
41             tree[b][a] = 1;    
42         }
43         ac = 0;
44         dfs(1);//从根节点开始 
45         cout << (ac ? "No" : "Yes") << endl;
46         //printf(ac ? "No
" : "Yes
") ;        
47     }
48     return 0;
49 }