#1996 [HNOI2008]神奇的国度

大意:
给一个无向图,用最少种颜色染色,使得相邻点颜色不同。


是一个mcs问题,具体算法及详细背景参见:
https://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html


几点注意:

结论很微妙,要加深理解,就是求一个“完美序列”

优化方法要注意,因为数值规模不大,用链表来实现最大值查询,少一个log

这种染色就是打标记嘛,一个点肯定不能和相邻的方成一组,所以相邻的标记++

注:最初所有点都是0,因为相邻才会++

每次选 标记数 最大 的入队 ,每一次删除相当于增加了 标记为 i 号的集合,肯定要选最“冲突”的 删除

#include queue 
#include iostream 
#include cstdio 
#include cstring 
#include iomanip 
#include cmath 
#include string 
#include algorithm 
#define pf printf
#define sf scanf

Copyright © 2018 qy8千亿国际qy8千亿国际-qy8千亿国际app版 All Rights Reserved