下面是另一道搜索题目的解答过程
题目是《算法问题实战策略》中的一题
oj地址是韩国网站 连接比较慢 https://algospot.com/judge/problem/read/PICNIC
大意如下
输入 3 2 1 0 1 4 6 0 1 1 2 2 3 3 0 0 2 1 3 6 10 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 输出 1 3 4
也是上来就撸一把DFS
全部能够匹配完成则计数增加1
但是有很多重复计算
我试过记录关系对的时候 以数值大小为序 只能排除一部分重复计算
错误的代码:
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5
6 using namespace std;
7
8 /*
9 3
10 2 1
11 0 1
12 4 6
13 0 1 1 2 2 3 3 0 0 2 1 3
14 6 10
15 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
16 //====================================
17 1
18 3
19 4
20 */
21
22 int t;
23 int a, b;
24 int n, m;
25 typedef pair<int, int> PII;
26
27
28 bool isFriend(int i, int j, const vector<PII>& friendv)
29 {
30 int minIdx = min(i, j);
31 int maxIdx = max(i, j);
32
33 for (auto& e : friendv) {
34 if (e.first == minIdx && e.second == maxIdx)
35 return true;
36 }
37
38 return false;
39 }
40
41
42 int dfs(bool isChecked[],const vector<PII>& friendv)
43 {
44 int firstFree = -1;
45 for (int i = 0; i < n; i++) {
46 if (isChecked[i] == false){
47 firstFree = i;
48 break;
49 }
50 }
51
52 if (-1 == firstFree)
53 return 1;
54
55 int ret = 0;
56
57
58 for (int secondFree = firstFree + 1; secondFree < n; secondFree++) {
59 if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false
60 && isFriend(firstFree, secondFree, friendv)) {
61 isChecked[firstFree] = true; isChecked[secondFree] = true;
62 ret += dfs(isChecked, friendv);
63 isChecked[firstFree] = false; isChecked[secondFree] = false;
64 }
65 }
66
67
68 return ret;
69 }
70
71
72
73
74 int main()
75 {
76 cin >> t;
77
78 while (t--) {
79 cin >> n >> m;
80 vector<PII> friendv;
81 bool isChecked[160] = {false};
82 while (m--) {
83 cin >> a >> b;
84 friendv.push_back({min(a,b),max(a,b)});
85 }
86 sort(friendv.begin(), friendv.end());
87 cout << dfs(isChecked, friendv);
88 }
89
90
91 return 0;
92 }
View Code
经过调试 发现DFS中双重循环有很大问题
i=0时候检测出 0 1配对 然后检测出2 3 配对.
但是当i=2时 也能检测2 3 配对 以及 0 1 配对。
于是做了以下修改，解决重复问题
ac代码
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4
5
6 using namespace std;
7
8 /*
9 3
10 2 1
11 0 1
12 4 6
13 0 1 1 2 2 3 3 0 0 2 1 3
14 6 10
15 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5
16 //====================================
17 1
18 3
19 4
20 */
21
22 int t;
23 int a, b;
24 int n, m;
25 typedef pair<int, int> PII;
26
27
28 bool isFriend(int i, int j, const vector<PII>& friendv)
29 {
30 int minIdx = min(i, j);
31 int maxIdx = max(i, j);
32
33 for (auto& e : friendv) {
34 if (e.first == minIdx && e.second == maxIdx)
35 return true;
36 }
37
38 return false;
39 }
40
41
42 int dfs(bool isChecked[],const vector<PII>& friendv)
43 {
44 int firstFree = -1;
45 for (int i = 0; i < n; i++) {
46 if (isChecked[i] == false){
47 firstFree = i;
48 break;
49 }
50 }
51
52 if (-1 == firstFree)
53 return 1;
54
55 int ret = 0;
56
57
58 for (int secondFree = firstFree + 1; secondFree < n; secondFree++) {
59 if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false
60 && isFriend(firstFree, secondFree, friendv)) {
61 isChecked[firstFree] = true; isChecked[secondFree] = true;
62 ret += dfs(isChecked, friendv);
63 isChecked[firstFree] = false; isChecked[secondFree] = false;
64 }
65 }
66
67
68 return ret;
69 }
70
71
72
73
74 int main()
75 {
76 cin >> t;
77
78 while (t--) {
79 cin >> n >> m;
80 vector<PII> friendv;
81 bool isChecked[160] = {false};
82 while (m--) {
83 cin >> a >> b;
84 friendv.push_back({min(a,b),max(a,b)});
85 }
86 sort(friendv.begin(), friendv.end());
87 cout << dfs(isChecked, friendv)<<endl;
88 }
89
90
91 return 0;
92 }
View Code