企业官网建设流程全解析

我最初学2-SAT的时候，觉得这东西就是“模板一背，拆点建边，跑个Tarjan看有没有变量真假点在同一个强连通分量里”。直到在练习系列第二张卷子里碰到一道带区间限制的题：如果按朴素办法建图，边数直接是约束数量乘以区间长度，最坏能到10^10量级，建图环节就已经判死刑了。那一题让我把重心彻底从“2-SAT怎么写”转移到“2-SAT怎么建图才不爆”。这篇博文就把这个短板一次性补上，重点拆解两类优化建图：一类是线段树优化区间连边，一类是用辅助节点把“至多一个”的O(k^2)边数压成O(k)。适合已经会基础2-SAT模板、但一碰边数就头疼的选手。

1. 从“会模板”到“边数爆炸”，中间隔着什么

1.1 先把基础2-SAT的两件事钉死

在聊优化之前，节点约定和答案判定必须统一，不然后面代码全是隐患。我习惯这样拆点：变量i为假，记作2*i；变量i为真，记作2*i+1。每个形如“a取av 或 b取bv”的约束，写成两条蕴含边：

• 如果a不满足av，那么b必须满足bv，建边not_a -> b取值bv的节点
• 如果b不满足bv，那么a必须满足av，建边not_b -> a取值av的节点

跑完Tarjan之后，如果某个变量真假点在同一个强连通分量里，无解。输出方案的时候，判断方式是if (scc[2*i] > scc[2*i+1]) 变量i为真 else 变量i为假。原理不复杂：Tarjan给SCC编号是按出栈顺序编号的，先出栈的编号小。如果存在A -> B的路径且A、B不同SCC，那么B所在SCC一定先出栈，所以scc[A] > scc[B]。因此false点 -> true点存在路径时，false点编号更大，此时不能选false，只能选true，反之亦然。

很多新人卡在答案输出上，其实是没把“编号大代表拓扑序靠前”这件事理顺。先阶段性地记住结论，等做优化建图时，这个结论能帮你快速手算样例，验证建图方向对不对。

1.2 朴素建图死在什么地方

我练习卷里那道题换成一个更直觉的模型：有n个按钮，每个按钮可以按下也可以不按。给定m条普通约束，每条说“按钮u和按钮v至少有一个被按下”。另外给q条区间约束，每条说“如果按钮x被按下，那么区间[l,r]里的所有按钮都不能被按下”。

区间约束等价于一堆子句：

对每个 j in [l,r]：(x不按) 或 (j不按)

这个形式是标准2-SAT子句，朴素做法是把每个j都拿出来，给每个j加两条边。一条区间约束如果长度是len，就要加2*len条有向边。当q和len都来到10^5时，总边数奔着10^10去，Tarjan的O(V+E)根本救不回来。

这类题的关键就是：不能把区间里每一个点都单独连一遍，必须让“一条边”能够覆盖一整段连续区间。这就是线段树优化建图要解决的事。

1.3 两类高频瓶颈模式

做优化建图题时，我一般先扫一遍约束，看它属于哪种模式：

• 点连向区间内的所有点，或者区间内所有点连向同一个点。典型就是“选了x，区间里全不能选”、“区间里有一个被选，就推出y成立”。
• 一个集合内至多选一个。典型是“每个组至多出一个代表”、“相邻位置不能同时选”，朴素做是组内两两连边，平方爆炸。

下面两节就是把这两种模式一个一个拆开，给出能直接用的建图方案。

2. 线段树优化建图：把“向区间连边”压到O(log n)

2.1 为什么要架一个线段树当中间层

想象一下，如果有一条公交线要从“某个点”把消息送到一栋楼里所有房间，你不会挨个房间塞纸条，而是把纸条送到这栋楼的总服务台，再靠楼层内部的通知系统传下去。线段树优化建图就是这个思路：区间节点相当于总服务台，父节点到子节点的树边相当于楼层通知通道。

具体到图里，如果要求从点from连向区间[l,r]内每个点，建立一个线段树，树边方向是父节点指向子节点。把区间[l,r]在线段树上拆成O(log n)个节点，from只需要向拆出来的这些节点分别加一条边。因为树边一路向下，from到达这些区间节点后，能顺着父到子的边覆盖区间内每一个叶子。

反过来，要表示“区间内每个点都连向点to”，树边方向换成子节点指向父节点。把区间拆成O(log n)个节点，每个拆出来的节点连向to，区间内任意一个叶子都能沿着子到父的路径到达这些节点再走到to。

2.2 正向树和反向树：别只建一边

这里是最多新手翻车的地方。2-SAT里一个子句从来不会是单方向的。以“如果x按下，区间[l,r]里全不能按”为例，对每个j，子句是(¬x ∨ ¬j)，它产生的两条蕴含边是：

• x为真 -> j为假
• j为真 -> x为假

第一条是“点连向区间内所有假点”，用父到子那棵树；第二条是“区间内所有真点连向固定假点”，必须用子到父那棵树。只优化其中一边，另一个方向仍然是逐条连边，复杂度照样是O(len)，而且更致命的是约束逻辑不完整，可能导致本来该无解的样例被判成有解。

所以在这道题里，我同时维护两棵线段树：

• 正向树：叶子直接复用变量i的假点2*i，树边父指向子，用来做“点 -> 区间内每个假点”
• 反向树：叶子直接复用变量i的真点2*i+1，树边子指向父，用来做“区间内每个真点 -> 点”

两棵树的节点编号不能混用，每一层递归的非叶子节点都要用new_node()从2-SAT类里申请新的节点编号。

2.3 核心代码与调用方式

以下代码可以直接作为模板，SegTreeOpt继承基础TwoSAT。基础TwoSAT负责维护图、Tarjan和判答案，SegTreeOpt负责在图上加线段树节点。

struct TwoSAT { int n, tot; vector<vector<int>> g; vector<int> dfn, low, scc, stk; vector<char> ins; int timer, scc_cnt; TwoSAT(int n_) : n(n_) { tot = 2 * n; g.resize(tot); } int new_node() { g.emplace_back(); return tot++; } void add_imp(int u, int v) { g[u].push_back(v); } // 约束：(a 取 av) 或 (b 取 bv) void add_or(int a, bool av, int b, bool bv) { int not_a = av ? 2*a : 2*a+1; // a 不满足 av 时的节点 int not_b = bv ? 2*b : 2*b+1; add_imp(not_a, 2*b + (bv ? 1 : 0)); add_imp(not_b, 2*a + (av ? 1 : 0)); } void tarjan(int u) { dfn[u] = low[u] = ++timer; stk.push_back(u); ins[u] = 1; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (ins[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { ++scc_cnt; while (1) { int v = stk.back(); stk.pop_back(); ins[v] = 0; scc[v] = scc_cnt; if (v == u) break; } } } bool satisfiable() { dfn.assign(tot, 0); low.assign(tot, 0); scc.assign(tot, 0); ins.assign(tot, 0); stk.clear(); timer = scc_cnt = 0; for (int i = 0; i < tot; ++i) if (!dfn[i]) tarjan(i); for (int i = 0; i < n; ++i) if (scc[2*i] == scc[2*i+1]) return false; return true; } vector<int> answer() { vector<int> res(n); for (int i = 0; i < n; ++i) res[i] = (scc[2*i] > scc[2*i+1]) ? 1 : 0; return res; } };

线段树树的部分直接继承并且在此基础上增加建树和区间连边：

struct SegTreeOpt : TwoSAT { int n; vector<int> out_node, in_node; SegTreeOpt(int n_) : TwoSAT(n_), n(n_) { out_node.assign(4*n, -1); in_node.assign(4*n, -1); build_out(1, 0, n-1); build_in(1, 0, n-1); } // 正向树：父 -> 子，叶子为假点 2*i void build_out(int p, int l, int r) { if (l == r) { out_node[p] = 2*l; return; } int m = (l + r) >> 1; build_out(p<<1, l, m); build_out(p<<1|1, m+1, r); out_node[p] = new_node(); add_imp(out_node[p], out_node[p<<1]); add_imp(out_node[p], out_node[p<<1|1]); } // 反向树：子 -> 父，叶子为真点 2*i+1 void build_in(int p, int l, int r) { if (l == r) { in_node[p] = 2*l+1; return; } int m = (l + r) >> 1; build_in(p<<1, l, m); build_in(p<<1|1, m+1, r); in_node[p] = new_node(); add_imp(in_node[p<<1], in_node[p]); add_imp(in_node[p<<1|1], in_node[p]); } // 点 from -> [ql,qr] 内每个点的假点 void add_point_to_interval_false(int from, int ql, int qr, int p, int l, int r) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { add_imp(from, out_node[p]); return; } int m = (l + r) >> 1; add_point_to_interval_false(from, ql, qr, p<<1, l, m); add_point_to_interval_false(from, ql, qr, p<<1|1, m+1, r); } // 区间 [ql,qr] 内每个点的真点 -> 点 to void add_interval_true_to_point(int ql, int qr, int to, int p, int l, int r) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { add_imp(in_node[p], to); return; } int m = (l + r) >> 1; add_interval_true_to_point(ql, qr, to, p<<1, l, m); add_interval_true_to_point(ql, qr, to, p<<1|1, m+1, r); } };

调用时，区间约束“x按 => [l,r]里全不按”这样写：

// 约束子句集：对每个 j in [l,r]，(x为假 或 j为假) add_point_to_interval_false(2*x+1, l, r, 1, 0, n-1); add_interval_true_to_point(l, r, 2*x, 1, 0, n-1);

注意外层调用时2*x+1是x的真点，2*x是x的假点，这两个方向分别对应子句的两个蕴含。漏掉第二个调用，小数据可能碰巧能过，大数据或特意构造的反例会让你WA得很困惑。

2.4 正确性和复杂度

正确性其实可以看作两条传递链：

• from -> 区间节点 -> 树边向下 -> 任意叶子假点，等价于from连向区间内每个j的假点。
• 区间内任意叶子真点 -> 沿反向树向上 -> 区间节点 -> to，等价于区间内每个j的真点连向to。

因为区间被拆成O(log n)个节点，每个区间约束只需要向树加O(log n)条边，建树本身每个内部节点两条树边，总复杂度O((n+q)log n)。空间上，两棵线段树各有约n个内部节点，总共增加约2n个图节点，还在可接受范围。

这里有个正确性细节：线段树拆出来的节点只是中转站，不会引入原公式不存在的推导。原因是边的方向是单向的，从区间节点出发只能到达它覆盖的叶子，叶子之间没有通过树边互相连通的路径。因此不会凭空产生新的矛盾或新的解。这也是为什么必须严格区分正向树和反向树，不能把两棵树混着建，否则树边可能把不属于区间的节点也串进去。

3. “至多一个”约束的链式优化：双链防止漏约束

3.1 朴素O(k^2)子句从哪来

“某个集合内至多选一个”在2-SAT里是一个非常自然的约束：集合内任意两个变量不能同时为真。于是朴素建图就是对集合内每个有序点对i < j加子句(¬a_i ∨ ¬a_j)，每条子句产生两条边：

• a_i真 -> a_j假
• a_j真 -> a_i假

一个大小为k的集合，子句数是C(k,2)，有向边数是k(k-1)。当k到10^5，平方根本无法接受。但如果用辅助节点串成链，边数能压到O(k)。

3.2 前缀链为什么不够：一个会让SCC“误判”的反例

我最早图省事，只给每个组加一条前缀链。定义辅助点pre[i]表示“前i个点中已经选了至少一个”，然后加边：

• a_i -> pre[i]
• pre[i-1] -> pre[i]
• pre[i-1] -> a_i取假

看起来已经阻止了“前面选过，后面又选”的情况。但这里有个致命问题：2-SAT子句的条件是对称的，只建一个方向的蕴含，SCC判定并不总是能发现矛盾。

拿k=2做个最小反例。假设a0和a1都被强制为真，同时要求“a0和a1至多一个为真”，这当然无解。用只加前缀链的建法，边是：

• a0 -> pre0
• pre0 -> pre1
• pre0 -> not a1
• 强制a0为真：not a0 -> a0
• 强制a1为真：not a1 -> a1

现在跑路径：a0 -> pre0 -> not a1 -> a1，因此a1的假点能到a1的真点。但a1的真点没有路径回到a1的假点，也没法走到not a0。于是SCC判定认为a0和a1的真假点都不在同一强连通分量里，会给出“有解”的错误结论。

问题出在遗漏了a1 -> not a0这条方向。两个点同时为真时，需要两个方向都走到对方的假点，才能把两个真假点圈进同一个SCC。这提醒我一个经验：2-SAT优化建图不是“能表达某个方向就够了”，而是必须保证每个子句产生的两条蕴含路径都存在。

3.3 前缀+后缀双链的正确建法

为了把两个方向都补全，对每个组同时建前缀链和后缀链。还是用辅助点pre和suf，含义分别是“前i个里已有至少一个为真”“后i个里已有至少一个为真”。

对组内点a0, a1, ..., a(k-1)：

• 每个a_i连向pre[i]和suf[i]
• pre[i-1] -> pre[i]
• suf[i+1] -> suf[i]
• pre[i-1] -> a_i取假，用于阻止前面已经选过时再选i
• suf[i+1] -> a_i取假，用于阻止后面已经选过时再选i

这样对任意i<j：

• 如果a_i和a_j同时为真，a_i能沿着pre链走到pre[j-1]，再走到a_j取假，于是a_j的真假点被打通。
• 反向，a_j能沿着suf链走到suf[i+1]，再走到a_i取假，于是a_i的真假点也被打通。

无论哪一对出现两个同时为真，SCC都能准确抓到。这个结构才是“至多一个”的完整线性建图。

3.4 双链代码与复杂度

代码实现上，我封装成一个函数，传入组内所有变量的真点编号：

// nodes 是同一组内每个变量的“真点”编号，调用前确保是 2*v+1 void add_at_most_one(vector<int> nodes) { int k = (int)nodes.size(); if (k <= 1) return; vector<int> pre(k), suf(k); for (int i = 0; i < k; ++i) { pre[i] = new_node(); suf[i] = new_node(); } for (int i = 0; i < k; ++i) { add_imp(nodes[i], pre[i]); // a_i -> pre_i add_imp(nodes[i], suf[i]); // a_i -> suf_i } for (int i = 0; i + 1 < k; ++i) { add_imp(pre[i], pre[i+1]); // pre_i -> pre_{i+1} add_imp(suf[i+1], suf[i]); // suf_{i+1} -> suf_i } for (int i = 1; i < k; ++i) { int not_ai = nodes[i] ^ 1; // 真点的异或1就是同一变量的假点 add_imp(pre[i-1], not_ai); // 前 i 个已有选 -> a_i 不能选 } for (int i = 0; i + 1 < k; ++i) { int not_ai = nodes[i] ^ 1; add_imp(suf[i+1], not_ai); // 后 i+1..k-1 已有选 -> a_i 不能选 } }

这段代码的节点数增加2k个，边数增加约6k条，整个“至多一个”组约束从平方量级降到线性量级。要注意的是，这个函数要求传入的是真点节点，也就是2*v+1，不能把假点传进去，否则nodes[i] ^ 1会指向真点，逻辑全反。

4. 练习题怎么挑：两道题验证两种建图

4.1 练习题A：区间互斥型

题面可以自己改成这样：有n个储能站，第i站可以启动也可以不启动。给定m条约束，每条说“u站和v站至少启动一个”。另有q条安全约束，每条说“如果x站启动，那么区间[l,r]内所有站都不能启动”。问是否存在满足所有约束的启动方案。

这题就是第二节的标准应用。建图时用SegTreeOpt，对每一条安全约束调用：

add_point_to_interval_false(2*x+1, l, r, 1, 0, n-1); add_interval_true_to_point(l, r, 2*x, 1, 0, n-1);

跑完satisfiable()后再用answer()输出方案。这道题能验证你是否真的理解两棵树的配合。如果你只加第一个调用，构造数据时强制区间内某个j为真且x为真，程序会误判有解；加上第二个调用后，SCC才能把这对真假点圈起来。

4.2 练习题B：组内至多一个型

题面可以这样设计：有n名球员和k个俱乐部，每人恰好属于一个俱乐部。要求每个俱乐部至多选一名球员进最佳阵容。另有m条“球员u和v至少入选一个”的关系约束。问是否存在入选方案。

每个俱乐部就是一组，俱乐部内的球员真点节点收集起来直接调add_at_most_one。关系约束用普通的add_or(u, true, v, true)加进去。这题的坑在于俱乐部总数很大，所有俱乐部的辅助节点总量仍然是O(n)，不会爆。你可以把k个俱乐部依次处理，不要在每个俱乐部内部使用同一个pre数组，否则辅助节点串到别的组里会造成完全错误的效果。

4.3 综合进阶：PA2010 Riddle

如果想验证自己是不是真的把“至多一个”的链式优化吃透了，可以去翻PA2010 Riddle这道经典题。它把“每个国家内至多选一个首都”和“每条边至少一端是首都”两种约束同时放进一张图里，建图核心就是双链优化加普通OR约束。这道题的整体细节还有一些额外处理，但光是把“组内至多一个”的线性建图吃透，你已经解决了它最难的一半。做的时候建议先用小样例手动画路径，再对拍标准模板。

5. 实际调试中踩过的坑，提前帮你踩平

5.1 节点编号分配不当导致越界

线段树建树和辅助节点都会不断new_node，很多人在TwoSAT里先给数组开固定大小2*n，然后在优化建图时直接访问2*n+线段树节点，下标越界到飞起。正确做法是像前面代码一样，每次申请节点都用new_node返回编号，图g动态变长，Tarjan数组在satisfiable()里按最终tot重新assign。记住一个原则：任何虚拟节点不要手写编号，统一走new_node。

5.2 区间覆盖自身产生的自环

区间约束里x可能正好落在[l,r]内，于是正向树会加一条x真 -> x假的边。这不是错误，它表示“如果x选了，区间约束就不允许x选”，等价于x必须不选。但要注意，如果你同时还有另一条约束强制x为真，那么SCC就会判无解，这是正确行为。性能上，自环不会造成逻辑问题，但是在数据特别大时，大量自环会让g的邻接表多出很多无用边，可以在区间调用前判断一下，如果from对应的变量落在区间内且只是自环，可以选择跳过，但一般影响不大。

5.3 递归深度和内存评估

线段树build的递归深度只有O(log n)，问题不大。Tarjan的递归深度在最坏情况下可以到O(V)，当图是一条链的时候，V到60万个节点级别就可能爆掉系统栈。竞技场上遇到大图，我建议要么在编译参数里开栈，要么直接把Tarjan换成手写栈版本。另外，用vector<vector >存图，每个节点有一个vector头，节点总量到百万时内存开销并不低。如果用静态前向星存边，内存会更可控，但写起来麻烦一些。先估一下最终tot和总边数再动手，能省很多RE和MLE。

5.4 小样例验证建图方向

线段树建图最怕方向反了。我调试时最有效的一招是构造一个只有3个变量的小数据，在建图后输出每个节点跑完Tarjan的SCC编号，手动模拟一条关键路径，比如2*x+1 -> 区间节点 -> 2*j能不能真的走通。只要手动跑通一个点对，剩下的方向问题基本就能定位。这个小步骤花不了两分钟，但能省下至少半小时的对拍时间。

做优化建图的题做得多了，我养成了一个习惯：动手写代码前，先把节点分成三类——真实变量点、线段树节点、辅助链节点，在草稿纸上画清楚边从哪来、往哪去。这一步看着啰嗦，实际上比直接撸代码快得多。优化建图考的不是Tarjan，考的就是对“一条边到底代表什么”的敏感度，把方向和多方向蕴含想明白了，剩下的只是把模板敲上去而已。