题意

有一个芯片,芯片上有\(N\times N\)个插槽,可以在里面装零件。

有些插槽不能装零件,有些插槽必须装零件,剩下的插槽随意。

要求装好之后满足如下两条要求:

  1. 第\(i\)行和第\(i\)列的零件数目必须一样多。
  2. 第\(i\)行的零件数目不能超过总的零件数目的\(\frac{A}{B}\)。

求最多可以另外放多少个零件(就是除掉必须放的)。如果无解输出 impossible 。

分析

费用流建图。

为了保证每一行的零件数目不能超过总的零件数目的\(\frac{A}{B}\),我们枚举每一行最大的允许零件数量为\(k\)。

考虑建图:

  • 源点\(S\)向行\(i\)连边,代价为\(0\),流量为这一行最多可能存在的零件数量
  • 列\(i\)向汇点\(T\)连边,代价为\(0\),流量为这一列最多可能存在的零件数量
  • 行\(i\)向列\(i\)连边,代价为\(0\),流量为\(k\),限制每行每列最大的零件个数
  • 如果\((i,j)\)可以不放零件,那么行\(i\)向列\(j\)连边,代价为\(1\),流量为\(1\)

我们可以发现,最大流的情况下求最小的费用就是移除的零件数量,就是要最小化

而图中只有满流的时候才是满足题意的,因为零件无非只有放和不放两种,不放走第四种边,放走第三种边,显然流量必须跑满

 


发表评论

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