在线建站|网页制作|网站建设平台_微信里的小程序找不到了_怎么优化网站排名_百度竞价关键词价格查询工具

回溯

#include <iostream>using namespace std;
const int N = 110;
int n, m;
bool a[N][N]; //关系
int p[N][N]; //第N个考场的第几个座位坐的是谁
int minRoom = N;void dfs(int person, int roomCount){if(roomCount >= minRoom) return;if(person > n){minRoom = min(minRoom, roomCount);return;}for(int i = 1; i <= roomCount; i++){int seat = 1;while(p[i][seat] && !a[person][p[i][seat]]){seat++;}if(!p[i][seat]){p[i][seat] = person;dfs(person + 1, roomCount);p[i][seat] = 0;}}p[roomCount+1][1] = person;dfs(person+1, roomCount+1);p[roomCount+1][1] = 0;
};int main()
{cin >> n >> m;for(int i = 0; i < m; i++){int p1, p2;scanf("%d%d", &p1, &p2);a[p1][p2] = a[p2][p1] = true;}dfs(1, 1);cout << minRoom;return 0;
}