Brief description:

.矩形染色问题。要给 m×n 的矩阵上色，每个格子要求的颜色给定，有三种染色操作：

1. 给连续一段水平格子染成某种颜色，花费为 h。
2. 给连续一段水平格子染成某种颜色，花费为 v。
3. 给一个单独格子染成某种颜色，花费为 s。

要求花费最小的上色方案，注意不能给同一个格子先后染两种不同颜色。

Analysis:

Tags：最小割
建模1. 两层, 左右染色操作，若染色操作有交集则连一条边流量为 s。。
建模2. 四层，左右染色操作，中间两层格点（拆点），。。

。。（建模 1, Dinitz, 180ms。。
。。（建模 2, Dinitz, 10ms。？。

.. 注意，虽然最小割[S, T]中的边都是满流边，但满流边不一定都是最小割中的边。在某些特殊图中，很多初学者容易犯错，认为不用 DFS，就可以直接得出割 …
[Amber07], pg8

External link:

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=11876

Posted by xiaodao
Category: ZOJ