首页 > 分享 > 【JZOJ4718】准备食物2 题解

【JZOJ4718】准备食物2 题解

最新推荐文章于 2020-04-28 09:20:54 发布

rzO_KQP_Orz 于 2016-08-20 20:41:48 发布

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

题目大意

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

【20%】n,m<=8

&#xA0;&#xA0;&#xA0;&#xA0;&#xA0;&#xA0;" role="presentation">      暴力

【50%】没有宠物会反动

&#xA0;&#xA0;&#xA0;&#xA0;&#xA0;&#xA0;" role="presentation">      左边一排 n 个点表示 n 个宠物,右边一排 m 个点表示 m 种食物,S 连向每个宠物容量 1 费用 0 的边,每个宠物连向每种食物容量 1 费用 v[i][j] 的边,每种食物连向 T 容量 a[i] 费用 0 的边。跑最大费用最大流。

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

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

【100%小优化】

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

相关知识

【JZOJ4718】准备食物2 题解
狗狗能吃的2️⃣0️⃣种食物|新手养狗必看
如何准备养宠物狗?宠物狗饲养准备指南
对宠物狗毛发健康有益的食物
买仓鼠要准备什么东西?
宠物貂的食物
养仓鼠需要准备什么
新手龙猫准备需知
养宠物蛇需要准备什么东西
你知道吗?狗狗绝育前的准备

网址: 【JZOJ4718】准备食物2 题解 https://m.mcbbbk.com/newsview24131.html

所属分类:萌宠日常
上一篇: 这些食物请勿与宠物狗共享
下一篇: 很多人或许不知道,会对宠物健康带