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

  • 每一行的數(shù)字的和
  • 每一列的數(shù)字的和
  • 某些格子有特殊的大小約束,用大于號(hào),小于號(hào)和等于號(hào)表示

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

Solution

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

括號(hào)左邊的是該格下界,右邊是上界。圖中的節(jié)點(diǎn)分別對(duì)應(yīng)原來的行與列。

第一步,根據(jù)已有條件建圖:

image:p23962.jpg