1. 特殊边的分布规律

题目核心是：

网格是 R 行 C 列。

特殊边存在于某些相邻格子之间。

特殊边的分布规律：

第 1 行，第 1 列和第 2 列之间的边是特殊边。

垂直方向周期为 2：即所有奇数行，第 1 列和第 2 列之间都有特殊边。

水平方向周期为 4：在奇数行，第 5 列和第 6 列、第 9 列和第 10 列……之间也有特殊边。

另外，所有的奇数列与下一列之间都有特殊边，且所在的行编号从左到右都相等（意思是这些特殊边在同一行内是水平方向的，并且是奇数列→偶数列）。

综合起来，特殊边分为两类：

奇数行的某些相邻列之间的特殊边（由周期 4 规律和奇数列到下一列的规律共同作用）。

奇数列与下一列之间的特殊边（所有行都一样，不依赖行奇偶性？这里要小心，题目说“所有的奇数列与下一列之间都有特殊边，且所在行的编号从左到右都相等”，可能是指这些特殊边在同一行内水平方向，但行号是固定的，其实是指所有行都有？但前面又说垂直周期 2，所以这里可能是指：奇数列到下一列的特殊边出现在所有行，但某些特殊边只在奇数行出现，两者有重叠。）

其实更简单的理解方法：

画图可知，特殊边构成一个二分图——网格被特殊边划分成两组格子，类似国际象棋棋盘，但这里的“相邻”是指有特殊边相连的相邻。

---

2. “讨厌的形状”是什么

题目说：如果一些小方块排列成了它讨厌的形状（特殊边的位置也要如图中所示），即使经过旋转、翻转后排列成讨厌的形状，也同样讨厌。

结合“滑溜方块”游戏（类似俄罗斯方块），这里“讨厌的形状”很可能是指由特殊边连接的两个相邻格子都放了方块，即存在一条特殊边，两端都有方块。

因为如果两个相邻格子有特殊边且都有方块，就会形成“弃行”条件。

所以问题变成：

在特殊边构成的图上，我们有一个点集（有方块的格子），如果一条特殊边的两端都有方块，就会形成讨厌形状。 要去掉一些方块（花费金币），使得特殊边的两端不同时有方块。

---

3. 转化为图论问题

特殊边构成一个二分图： 我们可以将网格的格子按某种规则分成两个集合 A 和 B，使得所有特殊边只在 A 和 B 之间，不会在 A 内部或 B 内部。

那么“讨厌的形状”就是存在一条特殊边连接的两个点都在当前有方块的集合中。

我们要删除一些方块，使得没有特殊边的两端同时被保留。

这等价于：保留的方块集是一个独立集（在特殊边构成的图中）。

目标：最小化删除的方块的总花费 = 总花费 - 保留的方块的总花费。

所以问题变成：在二分图中，求最大权独立集。

---

4. 二分图建模

我们需要确定 A 和 B 的划分规则。

观察规律：

特殊边在奇数行：第 1-2 列、第 5-6 列、第 9-10 列……（模 4 为 1 和 2 列之间）。

特殊边在所有行：奇数列与下一列之间（即列 1-2, 3-4, 5-6, … 之间）。

其实这两个条件可以合并： 所有相邻的奇数列与偶数列之间都有特殊边，且这些偶数列的列号模 4 为 0 或 2？需要验证。

更简单的方法： 用 (x,y) 表示第 x 列第 y 行。

定义颜色：

$$color(x,y)=(x+y)\:mod\:2$$

不对，因为这样是普通棋盘染色，但这里的特殊边不是所有相邻格子都有，所以二分图划分要按特殊边来。

实际上，我们可以这样划分： 将所有格子分成两类：

如果 xmod2=1 且 ymod2=1，则属于 A；

如果 xmod2=1 且 ymod2=0，则属于 B；

如果 xmod2=0 且 ymod2=1，则属于 B；

如果 xmod2=0 且 ymod2=0，则属于 A。

这样，所有特殊边（奇数列与下一列之间）连接的是 A 与 B。 奇数行的额外特殊边（如 1-2, 5-6 等）也符合这个染色。

所以这是一个二分图，A 和 B 是上述划分。

---

5. 公式化

设：

$S_A$：在集合 A 中有方块的格子集合。

$S_B$：在集合 B 中有方块的格子集合。

$W_A = \sum_{p \in S_A} w_p, \quad W_B = \sum_{p \in S_B} w_p$。

在二分图中，最大权独立集 = 所有节点权重和 - 最小点覆盖权重。

根据 Kőnig 定理：在二分图中，最小点覆盖权重 = 最大匹配的权重（这里是点权，所以是最小点权覆盖）。

而最小点权覆盖可以用最大流（最小割）求解： 源点连 A 中点，容量为点权；B 中点连汇点，容量为点权； 特殊边（A 到 B）容量无穷大。

那么最小割的值就是最小点权覆盖的权重。

因此：

$$最大权独立集=总权重−最小点权覆盖$$ $$答案=总花费−最大权独立集=最小点权覆盖$$

所以我们要求的就是这个二分图的最小点权覆盖。

---

6. 特殊情况

因为特殊边的图是规则的，并且数据范围很大（n 最多 $10^5$但 R,C 可达 $10^9$），我们不能建出整个图，只能对有方块的格子建图。

但这里 A 和 B 之间可能有很多特殊边，但两个有方块的格子之间如果有特殊边，则它们必须分属 A 和 B，并且它们的坐标满足相邻且颜色不同。

相邻的判定：

两个格子 ($x_1$,$y_1$) 和 ($x_2$,$y_2$) 有特殊边，当且仅当：

1.同行且列相邻：$y_1 = y_2$ 且 $|x_1 - x_2| = 1$并且$x_1$是奇数列（即min($x_1$,$x_2$)mod2=1）。

2.或者同列且行相邻？题目没说垂直方向有特殊边，所以特殊边都是水平的。

所以特殊边全是水平的，并且只在奇数列与下一列之间。

因此，二分图 A、B 划分简化为：

设

$$c = \left\lfloor \frac{x-1}{2} \right\rfloor + y$$

其实更简单：

令 col=(x−1)+y， 如果 col mod 2=0，则属于 A，否则属于 B。

检查：

对于 (1,1)：col=1，mod 2=1，属于 B？不对，我们验证 (1,1) 和 (2,1) 有特殊边，它们应属于不同集合。 (1,1): col=1 → B (2,1): col=2 → A 不同集合，正确。

所以划分公式：

$$Set=((x−1)+y)\:mod\:2$$

0 → A，1 → B。

---

7. 算法

于是算法：

1.读入所有有方块的格子 (x,y,w)。

2.计算 side=((x−1)+y) mod 2，为 0 则放入集合 A（左集），为 1 则放入集合 B（右集）。

3.建立二分图：对于每个 A 中点 (x,y,w)，找它的右邻居 (x+1,y) 是否在 B 中（因为特殊边是奇数列到下一列，所以 x 为奇数时，边是 (x,y) 到 (x+1,y)）。 同样，对于 B 中点 (x,y,w)，如果 x 为奇数，则它的左邻居 (x−1,y) 在 A 中，也有边。

4.建图后跑最小点权覆盖（最大流）。

但 R,C 很大，我们只能对存在的点建图，用 map 定位点。

---

8. 最大流建图

源点 s 向每个 A 中点连边，容量 w。

每个 B 中点向汇点 t 连边，容量 w。

对于每个特殊边（即相邻且不同集合的点对），从 A 点向 B 点连边，容量 ∞。

跑最大流得到最小点权覆盖值，这就是答案。

---

9. 核心公式

二分图最小点权覆盖：

$$min vertex weight cover=max flow in constructed network $$

其中网络构造为：

s→u∈A，容量 $w_u$ ​v∈B→t，容量 $w_v$ u∈A,v∈B 若有特殊边，则 u→v，容量 ∞

答案：

$$最小花费=max flow$$

---

10. 最终结论

我们不需要显式写出 A,B 的数学条件，但划分规则是：

$$set(x,y)=((x−1)+y)\:mod\:2$$

0 为 A，1 为 B。

特殊边条件：

水平相邻且 x 为奇数。

这样就能在给定的 n 个点上建立二分图，跑最大流得到答案。