蓝桥杯2017年第八届真题-分考场

解题思路:

注意事项:

参考代码:

        static int n,min=100;
        static int arr[][];//用一个二维数组来表达考生人数;
        static int examRoom[][];//一个二维数组来表示考场数量
        static int examStuNum[];//一个一位来表示每一个考场的人数

     public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       n=sc.nextInt();//来表示考试参加的人数
       int m=sc.nextInt();//来表示m行数据
       arr=new int[n+1][n+1];//录入考生人数
       examRoom=new int[n+1][n+1];//录入考场数量
       examStuNum=new int[n+1];//定义每一个考场的数量
       int a,b;
       for (int i=1;i<=m;i++){
           //定义一个for来遍历我们每一个考场的人;
           a=sc.nextInt();
           b=sc.nextInt();
           arr[a][b]=1;
           arr[b][a]=1;
       }
       dfs(1,0);
       System.out.println(min);
   }
   static void dfs(int stunum,int examnum){
       if(examnum>=min)return;//如果考场数大于最小数就返回
       if(stunum>n){
           //如果所有的学生安排完了,得出最小考场数
           min=examnum<min?examnum:min;
           return;
       }
       //都不满足以上要求的话,就开始遍历考场
       for(int i=1;i<=examnum;i++){
           int j;
           for ( j=1;j<=examStuNum[i];j++){
               //如果考场上有人认识的话,就打破循环
               if(arr[stunum][examRoom[i][j]]==1){
                   break;
               }
           }
           //如果考场上的人都不认识的话我们就继续搜索
           if(j==examStuNum[i]+1){
               //将此考生加入考场
               examRoom[i][++examStuNum[i]]=stunum;
               //dfs继续搜索下一轮
               dfs(stunum+1,examnum);
               --examStuNum[i];
           }
       }
       //如果考场上的人都认识的话,就开辟一个新的考场
       //将考生放入新的考场作中
       examRoom[examnum+1][++examStuNum[examnum+1]]=stunum;
       //dfs继续搜索下一个
       dfs(stunum+1, examnum+1);
       //回溯
       --examStuNum[examnum+1];
   }
}