PAT A1053 Path of Equal Weight

解题思路

思路比较简单，就是使用结构体数组构建一个树，然后dfs遍历，在遍历的开始将index加入vector保存路径，在dfs函数最后要将这个index删除，就实现了在树的同一层是否选择这个值，从而保证vector中保存的是一条从根节点到叶节点的路径。当len==0时，也就是当前节点为叶节点时，将路径vector保存到二维vector数组ans中。这样就可以找出每一条路径！然后遍历ans，当和为s时将其保存到另一个二维vector数组res，设置cmp函数对res排序，最后输出即可。

注意

cmp函数一定要注意！先考虑!=的情况，在本题中，我一开始设置标志位，导致有一个测试点不通过，是因为不能保证每个对应值都作为对比的结果返回！！！

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
struct Node{
    int data;
    vector<int> child;
}nodes[maxn];
int n,m,s;
vector<int> vec;
vector<vector<int> > ans;
vector<vector<int> > res;

void dfs(int index){
    vec.push_back(index);
    int len=nodes[index].child.size();
    if (len==0){
        ans.push_back(vec);
    }
    for(int i=0;i<len;i++){
        dfs(nodes[index].child[i]);
    }
    vec.pop_back();
}
/*写比较函数一定要小心了！！！优先考虑!=的情况！
 * 注意一个测试用例：
 * 10 2 5
 * 10 3 3 6
 * */
bool cmp(vector<int>& a,vector<int>& b){
    int len=min(a.size(),b.size());
    for(int i=0;i<len;i++){
        if (a[i]!=b[i]) return a[i]>b[i];
    }
    return a.size()>b.size();
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;i++){
        scanf("%d",&nodes[i].data);
    }
    for(int i=0;i<m;i++){
        int id,k,x;
        scanf("%d%d",&id,&k);
        for(int j=0;j<k;j++){
            scanf("%d",&x);
            nodes[id].child.push_back(x);
        }
    }
    dfs(0);
    for (int i = 0; i < ans.size();i++) {
        int sum=0;
        for (int j = 0; j<ans[i].size();j++) {
            sum+=nodes[ans[i][j]].data;
        }
        vec.clear();
        if (sum==s){
            for(int j=0;j<ans[i].size();j++){
                vec.push_back(nodes[ans[i][j]].data);
            }
            res.push_back(vec);
        }
    }
    sort(res.begin(),res.end(),cmp);
    for(int i=0;i<res.size();i++){
        for(int j=0;j<res[i].size();j++){
            if (j!=0) printf(" ");
            printf("%d",res[i][j]);
        }
        if (i!=res.size()-1) printf("\n");
    }
    return 0;
}