*PAT_甲级_1053 Path of Equal Weight (30分) (C++)【数组排序/DFS】

目录

​​1，题目描述​​

​​ 题目大意​​

​​输入​​

​​输出​​

​​2，思路​​

​​数据结构 ​​

​​如何排序 ​​

​​如何设计DFS算法​​

​​3，心路历程​​

​​4，代码​​

1，题目描述

Sample Input:

20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

Sample Output:

10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

 题目大意

给出一棵树，每个节点对应一个权值和一个编号。另外给出一个数字S，求出所有从根节点到叶子节点的权值之和为S的路径，并输出路径中各节点的权值。若路径不唯一，则按照数组从大到小有序输出。

输入

1. 第一行：N节点总数 M非叶节点总数 S给定的值；
2. 第二行：N个节点的权值；
3. 其余M行：每个非叶节点的编号，所含子节点的个数，子节点的编号；

输出

1. 按序输出所有路径中节点的值；

2，思路

设计结构体存放节点数据。利用vector存储这棵树。对树进行DFS，并将路径中节点存入temp中，并将权值之和为S的路径temp存入paths中。

对paths进行排序，按序输出；

数据结构 

• struct node{int id, key；vector<int> next；} ：存放节点数据；
• vector<node> tree(100)：存放树的所有节点；
• vector<vector<int> > paths：存放所有符合条件的路径；

如何排序 

//头文件
#include<algorithm>

//自定义排序函数
bool cmp1(vector<int> a, vector<int> b){
    for(int i = 0; i < a.size() && i < b.size(); i++){
        if(a[i] != b[i])
            return a[i] > b[i];
    }
    return false;
}

//调用
sort(paths.begin(), paths.end(), cmp1);

如何设计DFS算法

//实现过程
void DFS(int start, int weight){        //start起点编号 weight当前的累加值
    weight += tree[start].key;
    temp.push_back(tree[start].key);    //注意区分 节点编号还是节点数据
    if(tree[start].next.size() == 0){
        if(weight == S){
            paths.push_back(temp);
        }
    }
    for(int i = 0; i < tree[start].next.size(); i++){
        DFS(tree[start].next[i], weight);
    }
    temp.pop_back();                    // 注意弹出!!!
}

//调用
DFS(0, 0);

3，心路历程

（感觉这一题真正恶心的地方，是对结果数组进行排序。。。）
 

没有对结果数组排序，别的都正确，然而只拿到了10分（看来排序是关键）

一开始想用sort对paths排序，然而没有用（并不是没有用，而是我代码的问题：将节点的编号存了起来，而不是节点的权值）。

然而使用了自定义的冒泡排序后，还有一个测试点2没通过，不过拿到了28分。然而我又陷入了沉思，排序没问题了（其实是有问题的），为什么还有测试点没过？？？（哈哈哈，上面的问题仍然存在，可能是运气爆棚，正好能通过例子）。

上网查询后，都说测试点2是只有一个根节点的数据 ，然而我的代码对只有一个根节点，也可以正常运行。。。（绝了，我甚至想动用重启大法，，，但细想作为科班出身的我，绝不应该怀疑编译器，便又继续探索。。。）

没办法，只好求助牛客爸爸，终于找到了错误的举例。（不知道如何用牛客网测试数据的同学，可以戳这里​​【PAT数据测试——牛客网】​​）

测试用例:
10 2 3
1 1 1 2 2 2 2 2 2 2
00 8 01 03 04 05 06 07 08 09
01 1 02

对应输出应该为:

1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 1 1

你的输出为:

1 2
1 1 1
1 2
1 2
1 2
1 2
1 2
1 2

 哎呦我去，怎么还是排序的问题。。。

没办法，只好从头捋一遍了。终于发现了奇怪的地方！

（配色有点奇葩，不喜勿喷，嘤嘤嘤）

真相大白了，就是把节点编号当成节点数据进行了运算。

4，代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct node{
    int id, key;
    vector<int> next;
};

int N, M, S;                            //N树的结点 M非叶节点的节点数目 S给定的权值

vector<vector<int> > paths;
vector<int> temp;
vector<node> tree(100);

void DFS(int start, int weight){        //start起点编号 weight当前的累加值
    weight += tree[start].key;
    temp.push_back(tree[start].key);    //注意区分 节点编号还是节点数据
    if(tree[start].next.size() == 0){
        if(weight == S){
            paths.push_back(temp);
        }
    }
    for(int i = 0; i < tree[start].next.size(); i++){
        DFS(tree[start].next[i], weight);
    }
    temp.pop_back();                    // 注意弹出!!!
}

bool cmp1(vector<int> a, vector<int> b){
    for(int i = 0; i < a.size() && i < b.size(); i++){
        if(a[i] != b[i])
            return a[i] > b[i];
    }
    return false;
}

int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt", "r", stdin);
#endif

    scanf("%d%d%d", &N, &M, &S);

    int k;
    for(int i = 0; i < N; i++){
        scanf("%d", &k);
        tree[i].key = k;
    }

    for(int i = 0; i < M; i++){
        int id, num, temp;
        scanf("%d %d", &id, &num);
        for(int j = 0; j < num; j++){
            scanf("%d", &temp);
            tree[id].next.push_back(temp);
        }
    }

    DFS(0, 0);
    sort(paths.begin(), paths.end(), cmp1);

    for(int i = 0; i < paths.size(); i++){

        printf("%d", paths[i][0]);
        for(int j = 1; j < paths[i].size(); j++){
            printf(" %d", paths[i][j]);
        }
        printf("\n");
    }

    return 0;
}