分段打表

2019-SWERC

 2020.10.17 00:09  2023.09.01 18:14  ACM  最短路  卡特兰数  分段打表  博弈论 󰈭 3196字

参考博客： https://www.cnblogs.com/heyuhhh/p/12941654.html K 图上的路径存在问题(?) ->建反图进行染色建反图，用rot的每个邻点去对整张图染色，被染色的点就意味着可以走到该颜色所代表的邻点。我们允许每个点最多被染色两次，这是因为rot的邻点一旦被超过一个点染色，那么就一定不合法；所以对图中每个点而言，如果其被染色次数大于等于2，那么其出边所对应的一系列点的更新也已经都完成，再次染色增加染色次数没有任何意义，并不会改变“不合法”这一性质。 ...