思路 :

这是一张密铺图,虽然不能像方格图那样染成两色,但是能按照 $(x+y+z)\bmod 3$ 染成三色(有点像P1231)。

观察发现,共振总是恰好包含三种颜色的水晶各一个。要用最小的代价“割断”共振。

等价于一个三层图,由若干个限制,每个分别选取每一层的一个点组成三元组 $(a,b,c)$ ,要求它们不能同时存在。

拆点,中间连权为点权的边。对于三元组 $(a,b,c)$ ,连边$(S,a_{in},\inf),(a_{out},b_{in},\inf),(b_{out},c_{in},\inf),(c_{out},T,\inf)$。这样就能限制必须割掉一个。

接下来就是最小割了。能够发现有一些边和点可以合并。

二楼丢代码。