题目粗心:

给定一颗树和每个结点的权值,求从所有根结点到叶子结点的门路,使得每条门路上的权值之和等于给定的常数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;}