算法问题实战策略 PICNIC

下面是另一道搜索题目的解答过程
题目是《算法问题实战策略》中的一题
oj地址是韩国网站连接比较慢 https://algospot.com/judge/problem/read/PICNIC
大意如下

输入

输出

也是上来就撸一把DFS
全部能够匹配完成则计数增加1
但是有很多重复计算
我试过记录关系对的时候以数值大小为序只能排除一部分重复计算
错误的代码:

 #include <iostream>

 #include <vector>

 #include <algorithm>

 using namespace std;

 /*

 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

 */

 int t;

 int a, b;

 int n, m;

 typedef pair<int, int> PII;

 bool isFriend(int i, int j, const vector<PII>& friendv)

 {

     int minIdx = min(i, j);

     int maxIdx = max(i, j);

     for (auto& e : friendv) {

         if (e.first == minIdx && e.second == maxIdx)

             return true;

     }

     return false;

 }

 int dfs(bool isChecked[],const vector<PII>& friendv)

 {

     int firstFree = -;

     for (int i = ; i < n; i++) {

         if (isChecked[i] == false){

             firstFree = i;

             break;

         }

     }

     if (- == firstFree)

         return ;

     int ret = ;

     for (int secondFree = firstFree + ; secondFree < n; secondFree++) {

         if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false

                 && isFriend(firstFree, secondFree, friendv)) {

             isChecked[firstFree] = true; isChecked[secondFree] = true;

             ret += dfs(isChecked, friendv);

             isChecked[firstFree] = false; isChecked[secondFree] = false;

         }

     }

     return ret;

 }

 int main()

 {

     cin >> t;

     while (t--) {

         cin >> n >> m;

         vector<PII> friendv;

         bool isChecked[] = {false};

         while (m--) {

             cin >> a >> b;

             friendv.push_back({min(a,b),max(a,b)});

         }

         sort(friendv.begin(), friendv.end());

         cout << dfs(isChecked, friendv);

     }

     return ;

 }

经过调试发现DFS中双重循环有很大问题
i=0时候检测出 0 1配对然后检测出2 3 配对.
但是当i=2时也能检测2 3 配对以及 0 1 配对。

于是做了以下修改，解决重复问题
ac代码

 #include <iostream>

 #include <vector>

 #include <algorithm>

 using namespace std;

 /*

 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

 */

 int t;

 int a, b;

 int n, m;

 typedef pair<int, int> PII;

 bool isFriend(int i, int j, const vector<PII>& friendv)

 {

     int minIdx = min(i, j);

     int maxIdx = max(i, j);

     for (auto& e : friendv) {

         if (e.first == minIdx && e.second == maxIdx)

             return true;

     }

     return false;

 }

 int dfs(bool isChecked[],const vector<PII>& friendv)

 {

     int firstFree = -;

     for (int i = ; i < n; i++) {

         if (isChecked[i] == false){

             firstFree = i;

             break;

         }

     }

     if (- == firstFree)

         return ;

     int ret = ;

     for (int secondFree = firstFree + ; secondFree < n; secondFree++) {

         if (firstFree != secondFree && isChecked[firstFree] == false && isChecked[secondFree] == false

                 && isFriend(firstFree, secondFree, friendv)) {

             isChecked[firstFree] = true; isChecked[secondFree] = true;

             ret += dfs(isChecked, friendv);

             isChecked[firstFree] = false; isChecked[secondFree] = false;

         }

     }

     return ret;

 }

 int main()

 {

     cin >> t;

     while (t--) {

         cin >> n >> m;

         vector<PII> friendv;

         bool isChecked[] = {false};

         while (m--) {

             cin >> a >> b;

             friendv.push_back({min(a,b),max(a,b)});

         }

         sort(friendv.begin(), friendv.end());

         cout << dfs(isChecked, friendv)<<endl;

     }

     return ;

 }

巴特西

算法问题实战策略 PICNIC

最新文章

热门文章