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

解题思路:

其实就是图的着色问题：给定顶点数和边，求至少需要多少种颜色对图进行涂色能是相邻顶点颜色不同。

注意事项:

参考代码:

#include <cstdio>
const int N = 105;

int G[N][N]; // 图的邻接矩阵 
int vis[N][N]; // vis[i][j] = t表示第i个考场里面第j个人是t 
int cnt[N]; // 记录每个考场种的学生数量（对应的vis） 
int n, m; // n为顶点数，m为边数 
int ans = 0x3f3f3f3f; // 初始化最小值（要最小先赋一个较大的值） 

void dfs(int id, int num) { // id表示第id个学生，num表示当前考场编号 
	if(num >= ans) { // 当前解已经大于当前最优解 
		return ;
	}
	if(id > n) { // 学生已经安排完了 
		if(ans > num) { // 更新当前最优解（不要用min可能超时） 
			ans = num;
		}
		return ;
	}
	for(int i = 1; i <= num; ++i) { // 先看之前分配为的考场里面能不能进去 
		int rnd = 0; // 表示id学生与第i个考场里面的人不认识的数量 
		for(int j = 1; j <= cnt[i]; ++j) { // cnt[i]表示第i个考场里面的人数 
			if(G[id][vis[i][j]] == 0) rnd++;
		}
		if(rnd == cnt[i]) { // 如果都不认识 
			vis[i][++cnt[i]] = id;
			dfs(id + 1, num);
			cnt[i]--; // 回溯 
		}
	}
	// 现有考场都不行，就要增加考场 
	vis[num + 1][++cnt[num + 1]] = id;
	dfs(id + 1, num + 1);
	--cnt[num + 1]; // 回溯 
}

int main() {
	int u, v;
	scanf("%d%d", &n, &m);
	while(m--) {
		scanf("%d%d", &u, &v);
		G[u][v] = G[v][u] = 1; // 无向图 
	}
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}