zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

逆序数（C++代码）正解：线段树(nlogn)单点查询区间更新
浏览：363

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

蓝桥杯2017年第八届真题-分考场（C++代码）图的染色

　　作者: zjh　　　　发表时间：2019-05-19 13:59:27 浏览：995　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-分考场

#include "stdio.h"
    #include "stdlib.h"
    #include "iostream"
    #include "string.h"
    #include "math.h"
    #include "algorithm"
    #include "queue"
    #include "vector"
    #include "map"
    
    using namespace std;
    
    const int maxn = 105;
    
    int G[maxn][maxn];    //关系表
    int n, m;
    int res = 10000;    //结果
    int KCRY[maxn][maxn];    //第i个考场的人员
    int RS[maxn];    //第i个考场的人数
    
    void dfs(int id, int kc){
       if(kc >= res){    //剪枝，当前如果有比已经得到的结果还大那就没必要继续递归下去了
           return ;
       }
    
       if(id > n){    //如果id>n则说明分配完了，取一个最小的考场总数
           res = min(res, kc);
           return ;
       }
    
        //枚举每个考场
       for (int i = 1; i <= kc; ++i) {
           bool flag = true;    //用于做标记
           for (int j = 1; j <= RS[i]; ++j) {
               if(G[id][KCRY[i][j]]){    //如果在关系图中id这个人认识当前考场中任意一个人则说明这个考场不能放id这个人
                   flag = false;
                   break;
               }
           }
    
        //如果id这个人在这个考场中谁都不认识，则把他插到这个考场中
           if(flag){
               RS[i]++;    //第i个考场人数+1
               KCRY[i][RS[i]] = id;    //把id这个人添加到这个考场人员中
               dfs(id + 1, kc);    //继续下一个人的试探，考场总数不变
               RS[i]--;    //回溯
           }
       }
    
        //如果所有的考场都有认识的人，或者没有考场，则新建一个考场，并把id这个人放到此考场中
       RS[kc + 1]++;    //下一个考场的人数+1
       KCRY[kc + 1][RS[kc + 1]] = id;    //把id添加到下一个考场人员中
       dfs(id + 1, kc + 1);    //继续下一个人的试探，这时考场总数要+1
       RS[kc + 1]--;    //回溯
    }
    
    int main(){
       scanf("%d%d", &n, &m);
       for (int i = 0; i < m; ++i) {
           int x, y;
           scanf("%d%d", &x, &y);
           G[x][y] = G[y][x] = 1;    //建立关系表
       }
    
        //从第一个人，第0间教室开始
       dfs(1, 0);
       cout << res << endl;
       return 0;
    }

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

文件应用-fwrite函数

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言训练-亲密数（C++代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

点我有惊喜！你懂得！

蓝桥杯2017年第八届真题-分考场（C++代码）图的染色

评论区

精彩推荐

C语言训练-排序问题<1> （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

sizeof的大作用（C语言代码）

1054题解

简单的a+b （C语言代码）

zjh

TA的其他文章

你可能喜欢

文件应用-fwrite函数

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

C语言训练-亲密数 （C++代码）

十->二进制转换 （C++代码）（零和负数需要特殊处理）

点我有惊喜！你懂得！

蓝桥杯2017年第八届真题-分考场 （C++代码）图的染色

评论区

精彩推荐

C语言训练-排序问题<1> （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

sizeof的大作用 （C语言代码）

1054题解

简单的a+b （C语言代码）

C语言训练-亲密数（C++代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

蓝桥杯2017年第八届真题-分考场（C++代码）图的染色

　　评论区

sizeof的大作用（C语言代码）