图的着色小计

问题引入

有 \(n\) 个小孩子，它们有 \(m\) 对讨厌关系，每对关系约定为小孩 \(p\) 与 小孩 \(q\) 不能再一起玩。
现在你要给这些小孩分组，求最少要分成几组才满足每组小孩都不会发生矛盾。

问题抽象

我们抽象这个问题。
关系可以想到二分图，但是每对关系会互相约束，显然不行。
那么可以想成是一个图，有矛盾就连一条边。

这样，我们真正的问题就引出水面：
给定一张图，给每个点染色，满足有边链接的两个节点不能染同一种颜色，求染色成功的最小颜色数。

问题解决

通常的，这是一个我们刚开始学算法的经典问题，我们直接使用 dfs 暴力染色，期望的时间复杂度是 \(O(\text{过不了})\) 它能顺利解决 \(n\le 8\) 的情况

这个时间复杂度十分辣鸡。

我们考虑 状压dp 。

令 \(G(S)\) 表示集合 \(S\) 染同一种颜色是否合法，这个可以在 \(O(2^n\times n^2)\) 内求出。要是你真的强迫，使用 \(O(2^nn)\) 也不是不行。

我们考虑一位位染色，每次都染一种色。

令目前集合为 \(T\) 那么有显然转移：\(f_T = \min([G(S-T)]\space f_S)(S\subset T)\)

然后就做完了。时间复杂度 \(O(3^n)\) 能解决 \(n\le 16\) 的情况。