题目粗心:
给定一颗树和每个结点的权值,求从所有根结点到叶子结点的门路,使得每条门路上的权值之和等于给定的常数S.如果有多条门路,依照门路的非递增序列输入
算法思路:
考查树的遍历,因为需要求从所有根结点到叶子结点的门路,很天然就想到应用先序遍历该树,并且应用$path$保留以后搜寻门路,$result$保留所有符合条件的门路,如果以后结点是叶子结点,那么就先将此结点增加到$path$中,而后再计算$path$总所有结点的总权重,如果和给定的S相等,那么就将$path$增加进$result$中。接着得回退,先将叶子结点退出$path$,而后再返回。如果当期结点不是叶子结点,那么就先将以后结点增加进$path$中,而后再递归遍历其每一个孩子结点,在每一个孩子都遍历结束后就将当期结点退出$path$,这样就实现了整个树的搜寻过程。搜寻完结后,$result$就保留了所有满足条件的门路,接着就是将$result$的每一条门路序列依照字典序从大到小排序,最初再输入即可。
留神点:
- 1、在不排序的状况下,能够取得10分,测试点0和2谬误。
- 2、测试点2的谬误和测试点5的段谬误均是因为排序函数的问题,首先得留神是对权值排序,不是结点的ID(这个很容易搞错),而后就是对于两个序列的正反比拟逻辑都得写,也就是对于同一个地位i,a[i]>b[i]和a[i]<b[i]的返回值都得明确写进去,并且,对于所有的齐全一样的序列,也得做解决,否则测试点5呈现段谬误,总结一点就是排序函数得对所有的可能状况作出解决。
提交后果:
AC代码:
#include<cstdio>#include<vector>#include<algorithm>using namespace std;struct Node{ int weight; vector<int> child;}node[110];vector<int> path;//以后搜寻门路vector<vector<int> > result;//所有满足条件的解bool cmp(vector<int> a,vector<int> b){ int len = min(a.size(),b.size()); for(int i=0;i<len;++i){ if(node[a[i]].weight>node[b[i]].weight){ return true; }else if(node[a[i]].weight<node[b[i]].weight){//这个不写会呈现测试点2谬误 return false; } } return a.size()>b.size();// 不写这个呈现段谬误 }void preTraverse(int root,int weight){ if(node[root].child.empty()){ // 叶子结点 path.push_back(root); // 计算以后门路的权值 int sum = 0; for(int i=0;i<path.size();++i){ sum += node[path[i]].weight; } if(sum==weight){ result.push_back(path); } //回退 path.pop_back(); return ; } //抉择以后结点 path.push_back(root); for(int i=0;i<node[root].child.size();++i){ preTraverse(node[root].child[i],weight); } path.pop_back();}int main(){ int N,M,S;//结点总数,非叶结点总数 ,待查问权值 scanf("%d %d %d",&N,&M,&S); for(int i=0;i<N;++i){ scanf("%d",&node[i].weight); } int ID,K; for(int i=0;i<M;++i){ scanf("%d %d",&ID,&K); int child; for(int j=0;j<K;++j){ scanf("%d",&child); node[ID].child.push_back(child); } } preTraverse(0,S); // 依照字典序逆序输入result的序列 sort(result.begin(),result.end(),cmp); for(int i=0;i<result.size();++i){ for(int j=0;j<result[i].size();++j){ printf("%d",node[result[i][j]].weight); if(j<result[i].size()-1) printf(" "); } printf("\n"); } return 0;}