蓝桥杯2017年第八届真题-分考场 （C语言代码）

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int rela[105][105];

int now[105][105];

int cut[105]={0};

int res=105;

int n,m;

void dfs(int id,int num)

{

if(num>=res)//如果当前状态下分配的教室数已经大于了最小的教室数，则不用继续下去了

return;

if(id>n)//如果当前分配的人数已经超过了人数，表示已经安排完了，则可以返回了

{

res=min(res,num);

return;

}

for(int i=1;i<=num;i++)//遍历当前开出的每个教室

{

int sz=cut[i];//当前遍历到的教室的人数

int rest=0;//用来计算第id个学生与多少个当前教室里的人不认识。

for(int j=1;j<=sz;j++)//对教室里的每个人进行查询，若不认识就rest++

if(rela[id][now[i][j]]==0)

rest++;

if(rest==sz)//如果第id个学生与当前教室里每个人都不认识，则把他分到这个教室里

{

now[i][++cut[i]]=id;

dfs(id+1,num);

cut[i]--;//回溯

}

}

    //如果有一个认识的，则重新开一间教室。

now[num+1][++cut[num+1]]=id;

dfs(id+1,num+1);

--cut[num+1];//回溯

}

int main()

{

cin>>n>>m;

memset(rela,0,sizeof(rela));

memset(now,0,sizeof(now));

while(m--)

{

int a,b;

cin>>a>>b;

rela[a][b]=rela[b][a]=1;

}

dfs(1,0);

cout<<res<<endl;

return 0;

}