有一个n*m的方阵,里面的数字未知,但是我们知道如下约束条件:
问:是否存在用正数填充这个方阵的方案,满足所有的约束,若有,输出之,否则输出IMPOSSIBLE。
这个模型可以转化为无源汇的带上下界可行流模型,不过其建图比较复杂。下面根据题目的第一个SAMPLE进行解说。根据题目给出的要求,我们有以下信息:
括号左边的是该格下界,右边是上界。图中的节点分别对应原来的行与列。
第一步,根据已有条件建图: