【JZOJ4718】准备食物2 题解

题目大意

  现在觉有 m 种食物,第 i 种食物有 a[i] 份。觉要为 n 个宠物按编号顺序分配食物,每个宠物需要 1 份食物。
  觉通过读心,得出了每个宠物吃了每种食物后的喜悦值。觉还发现,对于其中一些宠物,假设它的编号为 i,如果 1~i-1 的宠物中,超过 s[i] 个被分配了第 num[i] 种食物,那么它会反动。
  在不反动的情况下,求所有宠物的喜悦值之和最大。
  1<=n<=200, 1<=m<=100, 0<=喜悦值$v[i][j]$<=10^5

【20%】n,m<=8

  暴力

【50%】没有宠物会反动

  左边一排 n 个点表示 n 个宠物,右边一排 m 个点表示 m 种食物,S 连向每个宠物容量 1 费用 0 的边,每个宠物连向每种食物容量 1 费用 $v[i][j]$ 的边,每种食物连向 T 容量 a[i] 费用 0 的边。跑最大费用最大流。

【100%】n<=200, m<=100

  沿用50分的图,我们现在要把反动限制加上去。
  对于一个反动限制,大概就是对于第 j 种食物,限制它 1~i 的宠物流过来的流量。所以很直观地,把每个食物拆成 n 个点,原来第 i 个宠物向第j种食物的连边就连到第 j 种食物的第 i 个点,然后每种食物的第 i 个点连向第 i+1 个点(有限制就容量 s[i] 费用 0,否则容量 inf 费用 0)。
  然而这样拆点我们发现太浪费了,限制最多 n 个,我们却拆成了 n*m 个点。所以我们考虑合并那些没用的点,具体来说就是,对于第 j 种食物,它有多少个限制,就拆成多少个点(为了方便,我们可以把 a[i] 也看作是一种限制)。

【100%小优化】

  对于同为 num[i] 的限制 i 和 j,若 i < j 且 s[i]>s[j] ,显然限制 i 是没有用的。这个可以用栈实现。