首先还是类似 POJ 3469. Dual Core CPU 的最小割建模。 难点是对每个节点 i，我们需要构造辅助节点 i’，满足，如果存在满足条件的 j 在 T 割，那么 i’ 也一定在 T 割。 因为找 j 的过程是一个区间关系，暴力构造 i’ 的话边数太多。 类比确定染色方案后，查询结果这个问题，这个显然可以离散化 + 线段树（树状数组）， 我们发现可以使用线段树来刻画这些辅助节点以减少边…
首先还是类似 POJ 3469. Dual Core CPU 的最小割建模。 难点是对每个节点 i，我们需要构造辅助节点 i’，满足，如果存在满足条件的 j 在 T 割，那么 i’ 也一定在 T 割。 因为找 j 的过程是一个区间关系，暴力构造 i’ 的话边数太多。 类比确定染色方案后，查询结果这个问题，这个显然可以离散化 + 线段树（树状数组）， 我们发现可以使用线段树来刻画这些辅助节点以减少边…
讨论
登录后参与讨论
还没有评论，来说第一句吧。