[深度优先搜索] 宝藏收集

形貌
你是一名探险家，进入了一片秘密的森林。森林中有多个藏宝点，每个藏宝点中都埋有一定命量的宝藏。同时，藏宝点之间有许多路径连接，你可以沿着这些路径举行探险。给出藏宝点及其连接的数据后，你可以从任一处开始探险，然后沿着指定的路径继续前行（仅能选择一条路径），当无路径可走时，探险结束。计划一个探险方案，使你能收集到最多的宝藏。
在一个森林中有N（1 ≤ N ≤ 20）个藏宝点，每个藏宝点中埋有一定命量的宝藏。同时，给出藏宝点之间的连接路径。给出藏宝点及其连接的数据后，你可以从任一处开始探险，然后沿着指定的路径继续前行（仅能选择一条路径），当无路径可走时，探险结束。计划一个探险方案，使你能收集到最多的宝藏。
输入
输入由若干行构成。
1. 第1行只有一个数字，表示藏宝点的个数N。
2. 第2行有N个数，分别表示每个藏宝点中的宝藏数量。宝藏数量是正整数
3. 第3行至第N+1行表示藏宝点之间的连接情况：
(1) 第3行有 n-1 个数（0 或 1），表示第一个藏宝点至第 2 个、第 3 个 … 第 n 个藏宝点有无路径连接。如第 3 行为 1 1 0 0 0…0，则表示第 1 个藏宝点至第 2 个藏宝点有路径，至第 3 个藏宝点有路径，至第 4 个、第 5 个 … 第 n 个藏宝点没有路径。
(2) 第 4 行有 n-2 个数，表示第二个藏宝点至第 3 个、第 4 个 … 第 n 个藏宝点有无路径连接。
(3) ……
(4) 以此类推，第 N+1 行有 1 个数，表示第 n-1 个藏宝点至第 n 个藏宝点有无路径连接。（为 0 表示没有路径，为 1 表示有路径）。
注意：各个藏宝点之间为单向连接。编号高的点没有边连到编号低的点
输出
第一行表示探险次序，各藏宝点序号间以一个空格分隔，不得有多余的空格。（最后一个序号后也有空格）
第二行只有一个数，表示能收集到的最多宝藏数。效果不超过109
假如有多条路径都可以得到最多宝藏数量，则输出字典序最小的那一条。比方，
序列 1 2 3 的字典序小于 1 10 12
样例输入

1. 5
2. 10 8 4 7 6
3. 1 1 1 0
4. 0 0 0
5. 1 1
6. 1

复制代码

样例输出

1. 1 3 4 5
2. 27

复制代码

解题分析
本题是很明显的一道深度优先搜索的标题，我们需要合理计划一个dfs递归函数。首先，我们要存储好每个地方的宝藏数量，以及整个图关系的连通次序。这个时候我们还需要一些合理的观察，包管我们的输入。然后，由于本题需要记载最优路径，所以我们合理地使用vector这个容器，利用好它的push_back函数和erase函数，便于我们在递归的过程中实时更新。然后，我们发现需要比较路径之间的字典序，所以不妨全局重新定义vector中的小于“<”的比较运算。接着，我们在dfs中，首先给函数传入一个开始深度优先搜索的起点位置，然后我们设置一个flag作为标记，看看我们当前位置是否还能往下走，假如可以就把flag设置为1，假如不行的话就说明假如我们选择了这条路，那么当前的一个宝藏数量已经达到了最大了（注意在dfs的过程中我们同时也举行了回溯的操作）。我们就开始判断了，假如当前的价值更大，则我们记载下这条路径，假如价值和我们的最佳价值一致，那么我们就判断一下字典序，字典序小的作为我们的最终答案。最终输出我们选定的路径和得到的最佳宝藏数量即可。
代码实现

1. #include <iostream>
2. #include <cstdio>
3. #include <queue>
4. #include <bitset>
5. #include <map>
6. #include <set>
7. #include <algorithm>
8. #include <cstdlib>
9. #include <unordered_map>
10. #include <unordered_set>
11. #include <cmath>
12. #include <vector>
14. using namespace std;
15. int N;
16. int bz[21];
17. int reach[21][21]={0};
19. int ans=-1;
20. int nowValue=0;
21. vector<int> bestPath;
22. vector<int> nowPath;
24. bool operator<(const vector<int>& A, const vector<int>& B){
25.         int lena=A.size();
26.         int lenb=B.size();
27.         for(int i=0;i<lena;i++)
28.                 for(int j=0;j<lenb;j++){
29.                         if(A[i]<B[i]) return true;
30.                         else if(A[i]>B[i]) return false;
31.                 }
32.         return false;
33. }
35. void dfs(int k){
36.         int flag=0;
37.         for(int i=k+1;i<=N;i++){
38.                 if(reach[k][i]){
39.                         flag=1;
40.                         nowValue+=bz[i];
41.                         nowPath.push_back(i);
42.                         dfs(i);
43.                         nowValue-=bz[i];
44.                         nowPath.erase(nowPath.begin()+nowPath.size()-1);
45.                 }
46.         }
47.         if(flag==0){
48.                 if(nowValue>ans){
49.                         ans=nowValue;
50.                         bestPath.erase(bestPath.begin(),bestPath.end());
51.                         int len=nowPath.size();
52.                         for(int i=0;i<len;i++){
53.                                 bestPath.push_back(nowPath[i]);
54.                         }
55.                 }
56.                 else if(nowValue==ans){
57.                         if(nowPath<bestPath){
58.                                 bestPath.erase(bestPath.begin(),bestPath.end());
59.                                 int len=nowPath.size();
60.                                 for(int i=0;i<len;i++){
61.                                         bestPath.push_back(nowPath[i]);
62.                                 }
63.                         }
64.                 }
65.         }
66.         return;
67. }
69. int main(){
70.         scanf("%d",&N);
71.         for(int i=1;i<=N;i++){
72.                 scanf("%d",&bz[i]);
73.         }
74.         for(int i=1;i<=N-1;i++){
75.                 for(int j=i+1;j<=N;j++){
76.                         scanf("%d",&reach[i][j]);
77.                 }
78.         }
79.         for(int i=1;i<=N;i++){
80.                 nowValue=bz[i];
81.                 nowPath.push_back(i);
82.                 dfs(i);
83.                 nowPath.erase(nowPath.begin()+nowPath.size()-1);
84.         }
85.         int len=bestPath.size();
86.         for(int i=0;i<len;i++){
87.                 if(i==0)
88.                 printf("%d",bestPath[i]);
89.                 else
90.                 printf(" %d",bestPath[i]);
91.         }
92.         printf("\n%d\n",ans);
93.     return 0;
94. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。