PKU 3493 Chessboard Puzzle

本星期 Individual Training 的題目

聲明：以下算法的正確性有可疑...

---

題意：

給定一個 M×N (M, N ≤ 16) 的整數表格
每對相鄰而顏色不同的 entry，得到 score := 兩個數值的 product

現在為每一個 entry 填上黑／白色
使得 total score 最大化

---

分析：

依我來看，跟 Dual Core CPU 如出一轍
同樣是 binary labeling 問題：
建圖，找 minimum cut，把 node 分為兩類，使得：

• S reachable 的 node 屬於 Type 0
• 其它的 node 屬於 Type 1
  

只是這題更 general，要處理 -ve cost
所以... 不能直接應用 minimum cut

不過透過 min-cost flow 就能實現 minimum cost cut（這個 cut 可以 -ve）

---

算法：

Binary labeling via min-cost flow
（以 min-cut 進行 binary labeling 的推廣）

給每個 entry [i,j] 拆成兩點： [i,j,1] 及 [i,j,2]
期望 min-cost flow 可以求出一種 bi-coloring
使得 S reachable 的 node 填黑色
其它 node 填白色

同時地，我們想 minimize 一些東西...

　score maximization = "-score" minimization ---- (1)
　minimum cost flow = "cost" minimization ---- (2)
Equate (1) (2):
⇒ "-score" 成為 minimum-cost 之中的 cost

具體建圖方法如下：

1. 由 S 連一條 edge 至每個 [i,j,1]
   　cost := 0
   　capacity := 4
   
2. 由每個 [i,j,2] 連一條 edge 至 T
   　cost := 0
   　capacity := 4
3. 給每對 1st order neighbor - [i,j] 及 [x,y]
   從 [i,j,1] 連 1 條 edge 往 [x,y,2]
   　cost := - a[i,j] × a[x,y]　　（"-score"）
   　capacity := 1
4. 要滿足 maximum flow 的要求：
   由每個 [i,j,1] 連一條 edge 往 [i,j,2]
   　cost := 0
   　capacity := 4

若果沒有 4.，基於 maximum flow 的條件
表格最終會變成黑白相間

──上述建圖方法可以縮點簡化（好似係），只是拆點後分析會比較簡單

──可是這樣求出的 割 (Cut) 是否必然對應一個 bicoloring？
不過基於圖的特性，貌似是對的
嗯... 還要細心想想，有水過的嫌疑

最終答案 := -minimum total cost / 2