dfs搜索
剪枝：num是以前排教室出的所有安排的最少教室，如果我们这一次的排的教室已经多于现在的num了，就直接return就行了
a[i][j] 用此数组来记录两者之间认不认识
v[i][j] 表示第i个教室的第j个座位坐着的人
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 110; int a[N][N] ; int v[N][N] ; //v表示第i个教室的第j个座位 int n , m ; int num = N ;//表示当前的最优教室安排 void dfs(int x,int room){ if(room >= num ) return ;//比以前的最好情况差，直接返回 if(x > n ){ num = min(num , room) ;//其实这里直接num = room 就行 因为前面比sum大的已经返回了 return ; } int k = 1 ;//遍历教师的每一个座位 for(int j = 1 ; j <= room ; j ++){ k=1; while(v[j][k] && !a[x][v[j][k]]) k ++ ;//往后找 如果中间碰到了一个认识的人k就停止+1 if(!v[j][k]){ //如果找完遍历教室的人没有认识的就刚好把它安排在这个教室的k个座位 v[j][k] = x ; dfs(x+1,room); v[j][k] = 0 ; } } //所有的教室都有认识的，只能给这个人单独开一个教室 v[room+1][1] =x ; dfs(x+1,room+1) ; v[room+1][1] = 0 ; } int main(){ cin >> n >> m ; for(int i = 1 ; i <= m ; i ++){ int x,y ; cin >> x >> y ; a[x][y] = a[y][x] = 1 ; } dfs(1,1); cout << num << endl ; return 0 ; }
