*PAT_甲级_1053 Path of Equal Weight (30分) (C++)【数组排序/DFS】
source link: https://blog.51cto.com/u_15849465/5801413
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
目录
1，题目描述
题目大意
输入
输出
2，思路
数据结构
如何排序
如何设计DFS算法
3，心路历程
4，代码
1，题目描述
Sample Input:
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:
给出一棵树，每个节点对应一个权值和一个编号。另外给出一个数字S，求出所有从根节点到叶子节点的权值之和为S的路径，并输出路径中各节点的权值。若路径不唯一，则按照数组从大到小有序输出。
- 第一行：N节点总数 M非叶节点总数 S给定的值；
- 第二行：N个节点的权值；
- 其余M行：每个非叶节点的编号，所含子节点的个数，子节点的编号；
- 按序输出所有路径中节点的值；
设计结构体存放节点数据。利用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
哎呦我去，怎么还是排序的问题。。。
没办法，只好从头捋一遍了。终于发现了奇怪的地方！
（配色有点奇葩，不喜勿喷，嘤嘤嘤）
真相大白了，就是把节点编号当成节点数据进行了运算。
#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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK