有一个n*m的方阵,里面的数字未知,但是我们知道如下约束条件:

  • 每一行的数字的和
  • 每一列的数字的和
  • 某些格子有特殊的大小约束,用大于号,小于号和等于号表示

问:是否存在用正数填充这个方阵的方案,满足所有的约束,若有,输出之,否则输出IMPOSSIBLE。

Solution

这个模型可以转化为无源汇的带上下界可行流模型,不过其建图比较复杂。下面根据题目的第一个SAMPLE进行解说。根据题目给出的要求,我们有以下信息: image:p23961.jpg

括号左边的是该格下界,右边是上界。图中的节点分别对应原来的行与列。

第一步,根据已有条件建图:

image:p23962.jpg