有一個(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ù)題目給出的要求,我們有以下信息:
括號(hào)左邊的是該格下界,右邊是上界。圖中的節(jié)點(diǎn)分別對(duì)應(yīng)原來的行與列。
第一步,根據(jù)已有條件建圖: