关于算法-数据结构:PAT甲级1053-Path-of-Equal-Weight

27次阅读

共计 1931 个字符,预计需要花费 5 分钟才能阅读完成。

题目粗心:

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

正文完
 0