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