MCOI R4 Ex

w33z8kqrqk8zzzx33 · 2021-01-16 09:00:47 · 题解

Ex：【Dream SMP】

我们一个点一个点的过。

测试点 1：u=v 同时 a=b

无语，模拟即可。

测试点 2：n=100,m=1000

给贪心或者优秀剪枝。

测试点 3：n=100,m=12000, 测试点 4：n=1000,m=123456

给更优秀贪心或者剪枝。

测试点 5：等价于二分图染色

观察到永远有 a=b。当 a\ge 2 就全满足了 u=v，表示 u 不得染 a。

删掉这些边并且排序会发现剩下的边由 \{(u,0,v,0),(u,1,v,1)\} 构成，也就是说把所有节点染 0 或者 1，并且这些边不得染同样颜色。二分图染色即可。

测试点 6：等价于四分图染色

同样逻辑得到这个测试点是四分图染色。贪心或者别的方法即可。

测试点 7：等价于八分图染色

给贪心。

测试点 8：n=10^5,m=10^6

引入正解科技：SAT Solver。

SAT Solver 是一个解 SAT Problem，或者 Satisfiability Problem，的程序，应用各种启发式来快速解决带有格局的 SAT 问题。一个 SAT 问题可以这样形式化：

• 有 p 个 01 变量，需要让它们满足 q 组条件。
• 一组条件 a_1,a_2,\dots,a_x b_1,b_2,\dots,b_x 表示必定存在至少一个 1\le k\le x 使得变量 a_k 取值为 b_k。

当所有 x 小于等于 2 这是 2-SAT，否则是著名 NPC 问题。SAT Solver 具体怎么用启发式解决 SAT 我们这里不探讨，仅仅将这道题的 SAT 构造。

创建 8n 个 01 变量，每一个节点对应 8 个变量，每一个变量对应某个节点是否染某个颜色。

这些变量需要满足这些规则：

1. 一个节点至少染一个颜色。
2. 一个节点不得染大于等于两个颜色。
3. 对边 (u,a,v,b)，不得同时有 u 染 a 和 v 染 b。

第一类可以对每一个节点创建一组条件，x=8，a_1,a_2,\dots,a_8 为这个节点的颜色变量，b_1=b_2=\dots=b_8=1 来强制至少一个 a 是 1。

第二类可以对每一个节点创建 \binom{8}{2} 组条件，x=2，a_1,a_2 为这个节点的颜色变量的一对，b_1=b_2=0 来强制不得有一个节点有两个颜色变量同时为 1。

第三类就按照含义暴力创建，x=2，a_1,a_2 为对应变量，b_1=b_2=0。

用一个更进阶的 SAT Solver 会快一点，例如 kissat：https://github.com/arminbiere/kissat

测试点 9：n=2\times 10^4,m=10^6

一样做法。

测试点 10：n=10^4,m=10^6

现在会发现以上构造根本不可能跑出来。

会好奇，为什么 n 变得更小反而更难了呢？首先观察到数据随机，如果 n=10^9 之类所有颜色“乱”填都挺可能符合条件，n 越小边的重合就越多，就越难填。

考虑一个更优秀的构造，发现染色个数恰好是 8=2^3。

我们可以进而将直接维护 n 个变量，每一个变量取值是 0 到 7。我们的条件任然是（变量 u 不等于 a 或者 变量 v 不等于 b）。不等于在二进制下的意义就是至少有一位不同，所以我们将 SAT 变量替代为这 n 变量的对应二进制位，变量数减少到 3n。

多一点耐心会跑完。