官方题解（中文整理）

基于 Akshaj Arora 的官方题解整理。

子任务 1：所有约束都满足 \(x=y\)

这时每条约束都是：

\(a_x + a_x = z\)

也就是：

\(a_x = \frac{z}{2}\)

所以如果某个点出现在约束中，它的取值至多只有一个可能。

若出现以下情况，则无解：

• 某条约束的 \(z\) 是奇数
• 同一个变量被不同约束固定成不同值

否则，所有被固定的点是否能发电都可以直接判断；而没有被约束到的点，完全可以取 \(a_i=l_i\)，从而保证发电。

子任务 2：所有约束都满足 \(|x-y|=1\)

把每个变量看作图上的一个点，每条约束 \(a_x+a_y=z\) 看成一条无向边。

在这个子任务中，图的每个连通块都是一条链。对于一条链，只要选定某个代表点 \(x\) 的值，那么整条链上所有点的值都会被唯一确定。并且每个点 \(y\) 的值都可以写成：

\(a_y = c \pm a_x\)

于是该点能发电的条件：

\(l_y \le a_y \le r_y\)

就会转化成关于 \(a_x\) 的一个区间限制。换句话说，每根燃料棒都对应“代表点取值落在哪个区间时，它能发电”。

因此对于一条链，问题就变成：

• 给出若干个数轴区间
• 找一个整数点，使其落在尽可能多的区间中

这是一个经典问题，把所有区间端点排序扫描即可。

子任务 3：所有约束都满足 \(|x-y|\le 1\)

这个子任务相当于把前两个子任务合并。

先处理所有 \(x=y\) 的约束，看看哪些变量被固定，或者是否已经无解。

然后对每一条链分类讨论：

• 如果这条链中没有任何固定值，那么仍然使用子任务 2 的区间覆盖方法
• 如果链中已经有一个固定值，那么整条链上所有点的值都会被唯一确定，只要依次推出并统计有多少点落在自己的稳定区间内即可

如果同一条链中出现互相矛盾的固定值，那么答案就是 -1。

正解：一般图

在完整问题中，约束图不再一定是链，而是任意无向图。我们仍然对每个连通块独立处理。

任选连通块中的一个代表点 \(x\)，把它视为自由变量。对整块做一次 DFS，就能把每个点写成：

\(a_i = b_i \cdot a_x + c_i\)

其中 \(b_i\) 只可能是 \(1\) 或 \(-1\)。

如果遇到回边怎么办

若图中有环，那么同一个点可能通过不同路径被表示成两个式子。这会导出一个关于 \(a_x\) 的一次方程。它可能有三种情况：

• 无解：整个连通块无解
• 唯一解：若该解不是整数，同样无解；否则 \(a_x\) 被固定
• 恒成立：说明这个连通块仍保留一个自由变量

两种最终情况

DFS 结束后，每个连通块都会落入下面两种之一：

• 代表变量 \(a_x\) 被固定
• 代表变量 \(a_x\) 未被固定

这正对应子任务 3 中的两种情况：

• 若已固定，就把整块所有点的值算出来，统计能发电的数量
• 若未固定，就把每个点对 \(a_x\) 的可行范围化成区间，再求最大区间重叠数

把所有连通块的贡献相加即可。

复杂度

整张图只需线性遍历，每个连通块的区间事件也只处理一次，总复杂度为：

\(O((N+M)\log N)\)

可以通过全部数据。