PAT A1053 Path of Equal Weight

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 wordmeaningassignv.指定、分配

思路1： DFS，用一个数组Res记录当前路径上的node，如果到达叶子节点时刚好权重和==s，打印出Res中node的Weight

TIPS: 要求non-increasing输出，DFS应每次从孩子最右向左进行（输入时要将每个节点的child从小到大排好序）

code1:

#include <stdio.h> #include <iostream> #include <vector> #include <algorithm> using namespace std; const int maxn = 110; struct Node{ int data, weight; vector<int> child; }node[maxn]; bool cmp(int a, int b){ //Q: a.b要使用int，不能直接用Node a, Node b return node[a].weight < node[b].weight; } int n, m, s; //n节点数，m非叶节点数，s给出的权值 int Res[maxn]; void DFS(int root, int sizeRes, int sum){ if(sum > s) return; //当前权值超过s，直接返回 if(sum == s){ //当前权值==s,判断是否刚好走到一个叶节点 if(node[root].child.size() != 0) return; //未到叶子，直接返回 for(int i = 0; i < sizeRes; ++i){ //刚好到达叶节点，输出路径Res[] printf("%d", node[Res[i]].weight); if(i < sizeRes-1) printf(" "); else printf("\n"); } } int numChild = node[root].child.size(); for(int i = numChild-1; i >= 0; --i){ //要求non-increasing,故要从右（weight大）向左 Res[sizeRes] = node[root].child[i]; // DFS(node[root].child[i], sizeRes+1, sum+node[root].weight); //权值加的是下一次迭代的（孩子的） DFS(node[root].child[i], sizeRes+1, sum+node[node[root].child[i]].weight); } return; } int main(){ scanf("%d %d %d", &n, &m, &s); for(int i = 0; i < n; ++i){ scanf("%d", &node[i].weight); } for(int i = 0; i < m; ++i){ int f, num; scanf("%d %d", &f, &num); for(int j = 0; j < num; ++j){ int ch; scanf("%d", &ch); node[f].child.push_back(ch); } sort(node[f].child.begin() , node[f].child.end(), cmp); } DFS(0, 1, node[0].weight); return 0; }

如果改为用vector存储Res:每次递归时将递归元素（root）push进vector，回溯时（递归完这个元素时：从递归函数出来），将这个元素pop出去

code 1-2：

vector<int> Res; void DFS(int root, int sum){ Res.push_back(root); if(sum > s) return; if(sum == s){ if(node[root].child.size() != 0) return; for(int i = 0; i < Res.size(); ++i){ printf("%d", node[Res[i]].weight); if(i < Res.size()-1) printf(" "); else printf("\n"); } } int numChild = node[root].child.size(); for(int i = numChild-1; i >= 0; --i){ DFS(node[root].child[i], sum+node[node[root].child[i]].weight); Res.pop_back(); } return; }

思路2：直接用邻接矩阵vector<int> node[maxn]存储，看了下第一次写的，有点迷…

T2 code:

#include <bits/stdc++.h> using namespace std; const int maxn = 110; int n, m, s; int weight[maxn]; vector<int> node[maxn]; vector<int> ans; void DFS(int r, int sumW){ ans.push_back(weight[r]); if(node[r].size() == 0){ sumW += weight[r]; if(sumW == s){ for(int i = 0; i < ans.size(); ++i){ if(i == 0) printf("%d", ans[i]); else printf(" %d", ans[i]); } printf("\n"); } return; } for(int i = 0; i < node[r].size(); ++i){ int nex = node[r][i]; DFS(nex, sumW + weight[r]); ans.pop_back(); } } bool cmp(int a, int b){ return weight[a] > weight[b]; } int main(){ scanf("%d %d %d", &n, &m, &s); for(int i = 0; i < n; ++i) scanf("%d", &weight[i]); for(int i = 0; i < m; ++i){ int id, c_size, tmp; scanf("%d %d", &id, &c_size); for(int j = 0; j < c_size; ++j){ scanf("%d", &tmp); node[id].push_back(tmp); } sort(node[id].begin(), node[id].end(), cmp); } DFS(0, 0); return 0; }