题解 P3965 【[TJOI2013]循环格】

2019-01-14 10:33:54


费用流。

首先可以发现,在完美的循环格中每个格子的入度和出度都是 $1$ 。

把每个格子拆成两个点,入点 $in$ 和出点 $out$ 。

从源点向 $in_x$ 连容量为 $1$ 、费用为 $0$ 的边,从 $out_x$ 向汇点连容量为 $1$ 、费用为 $0$ 的边。

再考虑两个相邻的格子 $x$ 和 $y$ 间怎么连边。显然,如果 $x$ 本来就指向 $y$ ,就从 $in_x$ 向 $out_y$ 连容量为 $1$ 、费用为 $0$ 的边;否则,从 $in_x$ 向 $out_y$ 连容量为 $1$ 、费用为 $1$ 的边。

跑一遍最小费用最大流,最小费用就是答案。

代码见blog