Home PAT 1053 Path of Equal Weight
Post
Cancel

PAT 1053 Path of Equal Weight

Link

十分纠结的两点:

  1. 怎么在递归时存储路径;
  2. 怎么将路径按照 non-increasing 的顺序排序.

我的思路是:

  1. tree 记录每个非叶子结点的所有子节点, 用 father 记录每个节点的父节点. DFS 到最后一层时, 如果权重之和满足条件, 就只记下叶子结点 —— 即满足条件的路径的最后一个节点. 最后根据 father 向上一直找到根节点即可还原这条路径.
  2. 关于排序的问题: 不能在输入每个节点的所有子节点后就给子节点序列按照权重的 non-increasing 顺序排序, 因为同一节点的子节点中可能有相同的权重, 此时就需要根据子节点的子节点判断. 总之, 需要将路径全部存储起来之后再给所有路径排序. 排序方法也很简单. 由于路径是用 vector<vector<int>> 存储的, 所以直接 sort 就可以得到 non-decreasing 的顺序, 最后倒序输出即可. 这里需要注意的是, 将每条路径存入 vector<vector<int>>ans 的时候, 需要事先就将它们按照从根节点出发的顺序存进去, 对应的就是代码中的 reverse(temp.begin(), temp.end()). 不然 sort(ans.begin(), ans.end()) 就不是按照最终路径排序的.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,s;
int w[100],father[100];
vector<int>tree[100];
vector<int>leaves;
vector<vector<int>>ans;
void DFS(int root,int val){
    if(tree[root].size()==0){
        if(val+w[root]==s) leaves.push_back(root);
        return;
    }
    val+=w[root];
    for(int i=0;i<tree[root].size();++i)
        DFS(tree[root][i],val);
}
int main() {
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;++i)
        scanf("%d",&w[i]);
    for(int i=1;i<=m;++i){
        int id,k,x;
        scanf("%d%d",&id,&k);
        for(int j=1;j<=k;++j){
            scanf("%d",&x);
            tree[id].push_back(x);
            father[x]=id;
        }
    }
    DFS(0,0);
    for(int i=0;i<leaves.size();++i){
        vector<int>temp;
        int root=leaves[i];
        while(root){
            temp.push_back(w[root]);
            root=father[root];
        }
        temp.push_back(w[0]);
        reverse(temp.begin(),temp.end());
        ans.push_back(temp);
    }
    sort(ans.begin(),ans.end()); //对于二维数组,直接sort就可以non-decreasing排序了!
    for(int i=ans.size()-1;i>=0;--i){
        for(int j=0;j<ans[i].size()-1;++j)
            printf("%d ",ans[i][j]);
        printf("%d\n",ans[i][ans[i].size()-1]);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.