PAT A1053

也不难，使用DFS就能很好的解决问题；对于DFS的途中节点记录有两种方法，这个需要注意一下:1.使用vector模拟栈，每次递归的时候压栈或者弹栈，遇到符合要求的时候直接复制该栈保存；2.使用path数组，并且利用numnode来追踪path数组的长度，其中path[i]代表路径上第i个节点的编号。由于numnode限制了path的长度，所以无需弹栈或者入站操作，只需要覆盖即可；关于本题判断还有一个优化，就是在过程中每次sum>s直接弹出，比之前自己想判断叶子节点优化了不少；完整代码如下所示：#include<iostream>#include<stdlib.h>#include<stdio.h>#include<vector>#include<algorithm>using namespace std;using std::vector;const int maxn=110;int n,m,s;int path[maxn];struct node{ int weight; vector<int>child;}table[maxn];bool cmp(int a,int b){ return table[a].weight>table[b].weight;}void DFS(int index,int numNode,int sum){ if(sum>s) return; if(sum==s){ if(table[index].child.size()!=0) return; for(int i=0;i<numNode;i++){ printf("%d",table[path[i]].weight); if(i<numNode-1) printf(" “); else printf("\n”); } return; } for(int i=0;i<table[index].child.size();i++){ path[numNode]=table[index].child[i]; DFS(table[index].child[i],numNode+1,sum+table[table[index].child[i]].weight); }}int main(){ int root,leaf,num; scanf("%d%d%d",&n,&m,&s); for(int i=0;i<n;i++){ scanf("%d",&table[i].weight); } for(int i=0;i<m;i++){ scanf("%d%d",&root,&num); for(int j=0;j<num;j++){ scanf("%d",&leaf); table[root].child.push_back(leaf); } sort(table[root].child.begin(),table[root].child.end(),cmp); } path[0]=0; DFS(0,1,table[0].weight); system(“pause”); return 0;}