题意

给出一个矩阵的行和和列和,求这个矩是否存在,存在的话是否唯一,唯一的话求唯一解。

分析

最大流,考虑建图。

  • 所有的行\(i\)向列\(j\)连边,代价为\(k\),表示矩阵中的\((i,j)\)最大能填\(k\)
  • 源点\(S\)向所有行\(i\)连边,代价为行和
  • 所有列\(i\)向汇点\(T\)连边,代价为列和

这个图跑出来的最大流显然就是整个矩阵的和

如果有解的话,当且仅当最大流 = 行和 = 列和

现在考虑怎么判断解是否唯一,即判断最大流的方案时候唯一,我们只需要判断残余网络中是否存在大于\(2\)的环即可,当然这道题目可以在矩阵上操作。

唯一解显然就是\(n\times m\)条边的实际流量,就是原本的流量 – 残余网络流量。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注