当前位置:   article > 正文

蓝桥杯高频考点真题单——3.分考场

蓝桥杯高频考点真题单——3.分考场

分考场(DFS

7.分考场 - 蓝桥云课 (lanqiao.cn)

一开始以为是连通图,直接计算大哥数量即可,但是仔细一看,其实是类似于图着色问题,相邻两个部分的颜色不能相同,求最少多少颜色。

然后想用暴力循环来解决,循环学生、遍历教室,如果这个教室人都不认识这个学生,就加进去;如果所有教室的学生都认识他,那就新开一个教室。但是这样有一个大问题,比如如果有2个教室都可以放这个学生,那到底是哪个放呢?

所以,其实本题应该用一个DFS来做,遍历所有的情况,将这个学生在所有的能放的教室都放一遍。

错误思路:

  1. void bad()
  2. {
  3. for (auto it : stu) //遍历所有学生
  4. {
  5. bool ff = 0;
  6. for (auto curroom : room) //当前教室
  7. {
  8. bool f = 1;
  9. for (int peo : curroom)
  10. {
  11. if (g[it][peo] == 1) //如果有联系,不能放在这个教室
  12. {
  13. f = 0;
  14. break;
  15. }
  16. }
  17. if (f) //能放
  18. {
  19. curroom.insert(it);
  20. ff = 1;
  21. break;
  22. }
  23. }
  24. if (!ff) //如果该生没有加入任何一个教室
  25. {
  26. room.push_back({ it }); //创建一个新的考场,加进去
  27. }
  28. }
  29. }

但是我觉得题目有个问题,他也没说学生编号是从1~n,但是我看很多答案都是按照这个来的。

注意:

  1. check函数中,需要检查的是cur和p号教室所有学生的关系,所以应该是g[cur][room[p][i]]而不是 g[cur][i].

  2. dfs中,需要注意开一个新教室的条件:cnt+1<=n,并不是只有不能开的才可以新开一间教室,而是所有学生都有权利开一间新教室,只要新开这个教室后(cnt+1)总教室数量仍然不超过总人数(<=n)

  3. 注意,就算是新开,也要回溯

AC:

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. // 类似着色问题,相邻的不能同色,问你总共几个颜色
  5. // 没想到可以用dfs做,但是也正常
  6. // 具体一点,xi为i号学生,kj为j号考场,如果xi和kj中的某个学生认识,那就不能放在这个考场
  7. // 如果所有考场的考生xi都认识,那就需要开一个新的考场
  8. const int N = 102; //最多100人,最多100考场
  9. //改进,用邻接表
  10. int g[N][N] = {0};
  11. vector<vector<int>>room(N);
  12. int n, m; //n人,m数据
  13. int mincnt = 0x3f3f3f3f;
  14. bool check(int cur,int p)
  15. {
  16. for (int i = 0; i < room[p].size(); i++) //遍历该教室所有人
  17. {
  18. if (g[cur][room[p][i]] == 1) //有熟人
  19. return false;
  20. }
  21. return true;
  22. }
  23. void dfs(int cur,int cnt) //当前学生编号,当前教室数量
  24. {
  25. if (cnt >= mincnt) return; //剪枝,这种情况已经超过之前的最小值了,一定不是答案
  26. if (cur > n)
  27. {
  28. mincnt = min(cnt, mincnt); //更新最小的
  29. return;
  30. }
  31. for (int i = 1; i <= cnt; i++) //遍历所有教室
  32. {
  33. if (check(cur, i)) //如果当前学生在i教室没认识的人
  34. {
  35. room[i].push_back(cur); //加进去试试
  36. dfs(cur + 1, cnt); //下一个学生,教室数量没变
  37. room[i].pop_back(); //回溯
  38. }
  39. }
  40. if (cnt+1<=n)
  41. {
  42. room[cnt+1].push_back({cur}); //新增一个新教室并放进去
  43. dfs(cur + 1, cnt + 1);
  44. room[cnt + 1].pop_back();
  45. }
  46. }
  47. int main()
  48. {
  49. cin >> n >> m;
  50. int a, b;
  51. for (int i = 1; i <= m; i++)
  52. {
  53. cin >> a >> b;
  54. g[a][b] = g[b][a] = 1; //认识
  55. }
  56. dfs(1, 1);
  57. cout << mincnt;
  58. return 0;
  59. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/616559
推荐阅读
相关标签
  

闽ICP备14008679号