有一個n*m的方陣,里面的數字未知,但是我們知道如下約束條件:

  • 每一行的數字的和
  • 每一列的數字的和
  • 某些格子有特殊的大小約束,用大于號,小于號和等于號表示

問:是否存在用正數填充這個方陣的方案,滿足所有的約束,若有,輸出之,否則輸出IMPOSSIBLE。

Solution

這個模型可以轉化為無源匯的帶上下界可行流模型,不過其建圖比較復雜。下面根據題目的第一個SAMPLE進行解說。根據題目給出的要求,我們有以下信息: image:p23961.jpg

括號左邊的是該格下界,右邊是上界。圖中的節點分別對應原來的行與列。

第一步,根據已有條件建圖:

image:p23962.jpg