技术学习分享_一航技术 技术资讯 *PAT_甲级_1053 Path of Equal Weight (30分) (C++)【数组排序/DFS】

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

广告位

目录

​1,题目描述​

​ 题目大意​

​输入​

​输出​

​2,思路​

​数据结构 ​

​如何排序 ​

​如何设计DFS算法​

​3,心路历程​

​4,代码​


1,题目描述

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

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

 

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分(看来排序是关键)

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

 

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

 

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

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

 

上网查询后,都说测试点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

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

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

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

(配色有点奇葩,不喜勿喷,嘤嘤嘤)

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

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

 

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;
}

 

本文来自网络,不代表技术学习分享_一航技术立场,转载请注明出处。

作者: 一航技术

上一篇
下一篇
广告位

发表回复

返回顶部