自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:29:01，当前版本为作者最后更新于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$。

多一点耐心会跑完。