luogu P4003 无限之环

发布时间 2023-03-28 20:45:05作者: 275307894a

挺牛逼一题。

首先我们发现所有的限制之和相邻的点有关,因此这启发我们进行黑白染色。

染色后不妨设源点向白点连边,黑点向汇点连边,流量为这个点接口的大小。

看上去应该是费用流模型,但是这个费用不好处理。

首先来考虑只有一个接口的,费用是平凡的,只需要让相邻两个为 \(1\) ,对面的为 \(2\) 即可。

再来考虑有两个接口的并且不是直线型的,可以发现其两条水管选择原来和对面的费用是独立的,都为 \(1\),因此可以直接建边。注意需要新开两个点限制横向和竖向流量都只为 \(1\)

四个接口旋转了和没转是一样的,因此我们最后的任务是考虑三个接口的。我们仍然假设选择四个接口的费用独立,则可以列出方程:

\[\begin{cases}x_1+x_2+x_3=0\\x_2+x_3+x_4=1\\x_3+x_4+x_1=2\\x_4+x_1+x_2=1\end{cases} \]

容易发现这是可以解出来的,那么可以把所有费用乘 \(3\) 之后就可以费用流了。

submission