M_sea的博客

M_sea的博客

A Mengbier

题解 P5331 【[SNOI2019]通信】

posted on 2019-05-01 09:23:21 | under 题解 |

先考虑一个暴力的费用流做法。

把每个哨站拆成两个点 $i_1$ 和 $i_2$ 。

然后这样连边:

  • $s$ 向 $i_1$ 连容量为 $1$ 、费用为 $0$ 的边, $i_2$ 向 $t$ 连容量为 $1$ 、费用为 $0$ 的边。
  • $i_1$ 向 $t$ 连容量为 $1$ 、费用为 $W$ 的边。
  • 对于每个 $j<i$ , $i_1$ 向 $j_2$ 连容量为 $1$ 、费用为 $|a_i-a_j|$ 的边。

最小费用就是答案。

但是这样的边数是 $n^2$ 级别的,可以获得 $80$ 分的好成绩。

考虑减少边数。直接分治/主席树优化连边就可以把边数优化到 $n\log n$ 级别了。然后就可以过了。

具体实现及细节见代码