咖啡


私信TA

用户名:Tianxn

访问量:128057

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 8
经  验 26039
参赛次数 10
文章发表 197
年  龄 22
在职情况 学生
学  校 西安电子科技大学
专  业 软件工程

  自我简介:

解题思路:


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

注意事项:

参考代码:

#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;
}


 

0.0分

3 人评分

  评论区