赞
踩
一开始以为是连通图,直接计算大哥数量即可,但是仔细一看,其实是类似于图着色问题,相邻两个部分的颜色不能相同,求最少多少颜色。
然后想用暴力循环来解决,循环学生、遍历教室,如果这个教室人都不认识这个学生,就加进去;如果所有教室的学生都认识他,那就新开一个教室。但是这样有一个大问题,比如如果有2个教室都可以放这个学生,那到底是哪个放呢?
所以,其实本题应该用一个DFS来做,遍历所有的情况,将这个学生在所有的能放的教室都放一遍。
错误思路:
- void bad()
- {
- for (auto it : stu) //遍历所有学生
- {
- bool ff = 0;
- for (auto curroom : room) //当前教室
- {
- bool f = 1;
- for (int peo : curroom)
- {
- if (g[it][peo] == 1) //如果有联系,不能放在这个教室
- {
- f = 0;
- break;
- }
- }
- if (f) //能放
- {
- curroom.insert(it);
- ff = 1;
- break;
- }
- }
- if (!ff) //如果该生没有加入任何一个教室
- {
- room.push_back({ it }); //创建一个新的考场,加进去
- }
- }
- }
但是我觉得题目有个问题,他也没说学生编号是从1~n,但是我看很多答案都是按照这个来的。
注意:
check函数中,需要检查的是cur和p号教室所有学生的关系,所以应该是g[cur][room[p][i]]
而不是 g[cur][i]
.
dfs中,需要注意开一个新教室的条件:cnt+1<=n
,并不是只有不能开的才可以新开一间教室,而是所有学生都有权利开一间新教室,只要新开这个教室后(cnt+1)总教室数量仍然不超过总人数(<=n)
注意,就算是新开,也要回溯
AC:
- #include <iostream>
- #include <vector>
- using namespace std;
-
- // 类似着色问题,相邻的不能同色,问你总共几个颜色
- // 没想到可以用dfs做,但是也正常
- // 具体一点,xi为i号学生,kj为j号考场,如果xi和kj中的某个学生认识,那就不能放在这个考场
- // 如果所有考场的考生xi都认识,那就需要开一个新的考场
- const int N = 102; //最多100人,最多100考场
-
- //改进,用邻接表
- int g[N][N] = {0};
- vector<vector<int>>room(N);
- int n, m; //n人,m数据
- int mincnt = 0x3f3f3f3f;
-
- bool check(int cur,int p)
- {
- for (int i = 0; i < room[p].size(); i++) //遍历该教室所有人
- {
- if (g[cur][room[p][i]] == 1) //有熟人
- return false;
- }
- return true;
- }
-
- void dfs(int cur,int cnt) //当前学生编号,当前教室数量
- {
- if (cnt >= mincnt) return; //剪枝,这种情况已经超过之前的最小值了,一定不是答案
- if (cur > n)
- {
- mincnt = min(cnt, mincnt); //更新最小的
- return;
- }
-
- for (int i = 1; i <= cnt; i++) //遍历所有教室
- {
- if (check(cur, i)) //如果当前学生在i教室没认识的人
- {
- room[i].push_back(cur); //加进去试试
- dfs(cur + 1, cnt); //下一个学生,教室数量没变
- room[i].pop_back(); //回溯
- }
- }
- if (cnt+1<=n)
- {
- room[cnt+1].push_back({cur}); //新增一个新教室并放进去
- dfs(cur + 1, cnt + 1);
- room[cnt + 1].pop_back();
- }
- }
-
-
- int main()
- {
- cin >> n >> m;
- int a, b;
- for (int i = 1; i <= m; i++)
- {
- cin >> a >> b;
- g[a][b] = g[b][a] = 1; //认识
- }
-
- dfs(1, 1);
-
- cout << mincnt;
-
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。