ZOJ 2609. Crazy Painter

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