Description：

一个棋盘上有一些特殊线：

如果出现了以下四种图形为不合法，可以翻转：

有一些位置有格子，其他为空，每个格子删掉有代价，最小化代价使得不存在上述图形。

$1\leqslant n\leqslant 10^5$

Solution：

首先注意到那四种图形就是在特殊线左边选两个右边选两个，如果知道了这题是网络流的话就容易想到把这四个格子看成一个路径，然后就是求最小割，因此把棋盘如下染色：

1|2 4 3 1|2 4 3 4 2|1 3 4 2| 1|2 4 3 1|2 4 3 4 2|1 3 4 2| 1|2 4 3 1|2 4 3 4 2|1 3 4 2| 1|2 4 3 1|2 4

先把每个点拆点，之间连容量为代价的边，从源点向所有 $3$ 连 $INF$ ，从 $3$ 向 $1$ 连 $INF$ ， $1$ 向 $2$ 连 $INF$ ， $2$ 向 $4$ 连 $INF$ ，然后跑最小割就行了。

Code：