咖啡


私信TA

用户名:Tianxn

访问量:13796

签 名:

人一我百,人十我万

等  级
排  名 14
经  验 8591
参赛次数 1
文章发表 124
年  龄 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;
}


C语言网提供「C语言、C++、算法竞赛」在线课程,全部由研发工程师或ACM金牌退役选手亲自授课,以视频+配套题目的学练同步模式教学,强化动手,并提供增值服务!

  评论区