蓝桥杯历届试题分考场-白红宇

蓝桥杯历届试题分考场

阅读量：3904 次

发布时间：2019-05-23

本文共 704 字，大约阅读时间需要 2 分钟。

问题描述

　　n个人参加某项特殊考试。

　　为了公平，要求任何两个认识的人不能分在同一个考场。

　　求是少需要分几个考场才能满足条件。

输入格式

　　第一行，一个整数n(1<n<100)，表示参加考试的人数。

　　第二行，一个整数m，表示接下来有m行数据

　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

　　一行一个整数，表示最少分几个考场。

样例输入

1 2

1 3

1 4

2 3

2 4

2 5

3 4

4 5

样例输出

样例输入

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

4 5

样例输出

思路：

暴力搜索教室数目，然后注意剪枝，用vector会超时。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=1e2+5;int m,n;int edge[maxn][maxn];int num[maxn];int cal[maxn][maxn];int ans=0x3f3f3f3f;void dfs (int x,int tnum){    if(tnum>=ans) return;    if(x>n)    {        ans=min(ans,tnum);        return;    }    for (int i=0;i