传送门

洛谷翻译
CodeForces

Solution

emmm,先引入一个对偶问题的概念
\(max(c^Tx|Ax \leq b)=min(b^Ty|A^Ty \ge c)\)
考虑这个式子的现实意义:

  • \(c\):每种成品的收益
  • \(x\):每种成品生产多少个
  • \(A\):生产每种成品所需要的原料数
  • \(b\):每种原料的总个数
  • \(y\):直接卖原料、每种原料的价格

然后考虑第一个式子就是成品的最大收益对吧.
现在我们不做成品了,搞原料去,显然不能够亏,不然不如搞成品.
所以我的最小收益要和成品的最大收益相同(不然就有亏的可能).
然后就大概理解了吧.

代码实现

代码戳这里

05-08 08:07