历届试题 分考场

题目

问题描述

  n个人参加某项特殊考试。
  为了公平,要求任何两个认识的人不能分在同一个考场。
  求是少需要分几个考场才能满足条件。

输入格式

  第一行,一个整数n(1<n<100),表示参加考试的人数。
  第二行,一个整数m,表示接下来有m行数据
  以下m行每行的格式为:两个整数a,b,用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

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

样例输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

样例输出

4

样例输入

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出

5

题目大意

 n个学生,然后m个关系

在这m个关系中 两个学生相互认识,如果他们认识的话就不能在同一个考场,问最少分配几个考场就可以满足要求

 思路算法:dfs

 

 直接每个学生去安排,第一个学生肯定分配一个考场。

然后第二个学生,然后我们看考场,如果第一个考场满足条件(也就是第二个学生与第一个考场中的人互不认识),那么学生二可以在此考场,否则又新开辟一个考场。

为了不失一般性,我们假设现在已经安排了x-1个学生,已经分配了kn个考场,现在在安排第x个学生

首先我们依次枚举各个考场,如果第i个考场满足条件,学生x就进入i考场;如果i考场不满足条件,我们继续判断i+1考场。如此往复,当我们把kn个考场全部枚举完,发现学生x与每个考场都存在认识关系,那么我们必须为x新开辟一个考场了。

我们首先定义g[][]数组,用来维护考生之间的认识关系,g[a][b]=g[b][a]=1;

p[i][j]数组是用来表示第i个考场第j个座位是否有人,有人为1,无人为0; 

 while(p[j][k] && !g[x][p[j][k]]) k++; 

k是从0一直变化的,其实代表的就是考场中的座位号

for(int j=1;j<=kn;j++)						
{						
    int k=0;
    while(p[j][k] && !g[x][p[j][k]]) k++; 	
    if(p[j][k]==0)			
    {
        p[j][k]=x;
        dfs(x+1,kn);
        p[j][k]=0;
    }
}    

我们来讲解一下for和while循环

for循环枚举考场,每次k置0,因为每次我们要枚举考场座位号都是从0开始的

进入while

如果一开始p[j][k]==0 ,直接退出while,那么说明这个考场还没有人,考生当然可以坐在这个考场,执行if语句,开始安排下一个学生

一开始是p[j][k]==1,然后看g[x][p[j][k]]也就是看j考场中k座位的学生是否与x认识,如果认识那么退出,退出之后显然if语句不执行,我们只能继续看下一个考场是否可以安排他了

一开始是p[j][k]==1,最后退出不是因为这个考场中的学生与x认识,而是因为枚举到一个座位是空的,也就是p[j][k]==0,那么说明这个考场一个学生也不和x认识,而且有座位,x可以在这。

 

最后当我们for语句执行完了,也就是说所有考场中都有x认识的人,必须为x开辟一个新考场才行

代码

#include<bits/stdc++.h>
using namespace std;
int g[110][110],p[110][110];				
int n,num=110;
void dfs(int x,int kn)					 			//x考生数 kn考场数	
{ 
	if(kn>=num) return;					
  	if(x>n) 	{num=min(num,kn); return;}       
		
	for(int j=1;j<=kn;j++)						//枚举考场 
	{						
	   	int k=0;
		while(p[j][k] && !g[x][p[j][k]]) k++; 	/*找到一个空位 并且与该考场人无关系 */
		//j考场没有人 直接退出while 进入if语句 说明这个考生可以在这个考场
		//j考场有人 如果是因为考生与这个考场中的某个人认识而退出的话 p[j][k]肯定是为1 不执行if语句 接着看下一个考场	
		//j考场有人 是因为观察完此考场中所有的学生都与x考生互不认识推出的,那么if语句执行 
		if(p[j][k]==0)							//满足条件 进行下一考生 
		{
			p[j][k]=x;
			dfs(x+1,kn);
			p[j][k]=0;
		}
   	}                                  		 	  
	p[kn+1][0]=x;				//遍历完所有的考场 发现都不行 只能新开辟一个考场					
	dfs(x+1,kn+1);							
	p[kn+1][0]=0;									
}
int main()
{
	int m,a,b;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{ 
		cin>>a>>b;
		g[a][b]=g[b][a]=1; 			
	}
	dfs(1,1);
	cout<<num;
	return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

;

Popular Programs