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

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

#define N 301

#define min(a,b) a>b?b:a;

int gxb[N][N];//关系表

int p[N][N];//房间状态

int num=N,n;

void DFS(int x,int kcs)

{

if(kcs>=num)

return;//剪子

if(x==n+1)

{

num=min(num,kcs);

return;

} //如果已经安排了 n个人，惊醒判断

int j,k;

for(j=1;j<=kcs;j++)

{

k=0;

while(p[j][k]&&!gxb[x][p[j][k]])

    k++;//找到一空位，并且与该考场人无关

if(p[j][k]==0)

p[j][k]=x,DFS(x+1,kcs),p[j][k]=0;//满足条件，下一考生 

}

p[j][0]=x;

DFS(x+1,kcs+1);

p[j][0]=0;//回溯 

 }

 int main()

 {

  int m,i,s1,s2;

  memset(gxb,0,sizeof(gxb));

  memset(p,0,sizeof(p));

  scanf("%d\n%d",&n,&m);

  for(i=1;i<=m;i++)

  {

  scanf("%d%d",&s1,&s2);

  gxb[s1][s2]=gxb[s2][s1]=1;//键关系 

}

  DFS(1,1);

  printf("%d\n",num);

return 0; 

  }