题目分析

这是 POI 2012 Bezpieczeństwo minimalistyczne 的题解代码。题目要求：

• 无向图，点权 $p(v)$，边权 $b(u,v)$
• 初始条件：$p(u) + p(v) \ge b(u,v)$
• 目标：减少点权使得 $p(u) + p(v) = b(u,v)$ 对所有边成立
• 求减少的点权和的最小值和最大值

核心思路

1. 问题转化

代码将问题转化为：

add(x, y, a[x] + a[y] - z);

这里 a[x] 是原始点权，z 是边权 $b(u,v)$。
新边权 = $p(u) + p(v) - b(u,v)$，表示需要减少的总量。

2. 图的性质分析

代码处理两种特殊情况：

• 奇环：可以唯一确定点权减少量
• 偶环：可能产生矛盾

3. DFS 遍历

dfs 函数负责：

• 遍历连通分量
• 检测环并分类处理
• 记录深度信息用于判断奇偶环

4. 约束传播

check 和 get 函数负责：

• 在树结构上传播约束
• 计算每个点权减少量的可行范围 $[l_i, r_i]$
• 验证约束一致性

5. 最值计算

对于每个连通分量：

• 如果是奇环，点权唯一确定
• 如果是树或偶环，在可行域内分别取最小和最大减少量

关键算法点

1. 奇偶环处理

if ((dep[x] - dep[y]) % 2) {
    // 偶环：检查一致性
} else {
    // 奇环：计算唯一解
}

2. 约束传播

l[x] = max(l[x], w - r[y]);
r[x] = min(r[x], w - l[y]);

维护每个点减少量的上下界。

3. 可行性验证

检查所有约束是否满足：

return (l[x] > r[x]) | tmp;  // 上下界冲突

复杂度分析

• DFS 遍历：$O(n + m)$
• 约束传播：$O(n)$ 每个连通分量
• 总复杂度：$O(n + m)$

总结

这个解法是典型的图论+约束满足问题：

1. 将原问题转化为图上的约束系统
2. 利用图的连通性和环的性质分类处理
3. 通过约束传播确定可行域
4. 在可行域内计算最优值

代码巧妙地处理了奇偶环的不同性质，是竞赛中图论约束问题的经典解法。