有一個n*m的方陣,里面的數(shù)字未知,但是我們知道如下約束條件:
- 某些格子有特殊的大小約束,用大于號,小于號和等于號表示
問:是否存在用正數(shù)填充這個方陣的方案,滿足所有的約束,若有,輸出之,否則輸出IMPOSSIBLE。
Solution
這個模型可以轉化為無源匯的帶上下界可行流模型,不過其建圖比較復雜。下面根據(jù)題目的第一個SAMPLE進行解說。根據(jù)題目給出的要求,我們有以下信息:
括號左邊的是該格下界,右邊是上界。圖中的節(jié)點分別對應原來的行與列。
第一步,根據(jù)已有條件建圖: