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