题解【P3826 [NOI2017] 蔬菜】

更严谨的正确性分析。 更自然的非启发式思路。（然而也有点难想） 更强的扩展性。（然而也没做过几个题） ~~更多的草稿纸。~~ **广告** ： [模拟费用流小记](https://www.luogu.com.cn/blog/command-block/mu-ni-fei-yong-liu-xiao-ji) （建议阅读） ------------ **题意** : 有 $n$ 种蔬菜，第 $i$ 种蔬菜单价是 $a_i$，初始时数量为 $c_i$，若不出售，每天有 $x_i$ 份会变质。初次出售第 $i$ 种蔬菜可以获得 $s_i$ 的奖励。 每天可以卖掉 $m$ 个未变质的蔬菜。有 $k$ 个询问，每次问在 $1\sim p$ 天出售蔬菜能够获得的最大收益。 ------------ 首先解释一下题意。 **同种蔬菜中**，每棵蔬菜都有自己独立的变质时间，在不出售的情况下，效果是每天有 $x_i$ 份会变质。但可以出售这些较快变质的菜，保留那些较慢变质的菜。 - **正确理解** : 每天会有 $3$ 棵菜变质，则变质时间为 $\{1,1,1,2,2,2,3,3,3...\}$。若第一天卖掉了两棵 $[1]$ ，则只有一棵 $[1]$ 会变质。 - **错误理解** : 无论怎么卖，剩余的该种蔬菜都会变质 $3$ 个。 也可以理解为，将蔬菜再按照过期时间分类为不同类别的菜。 ------------ - $\small\blacksquare$ **费用流模型** 考虑**时间倒流**，问题变为 : 每天都会加入一些菜（原来会变质的菜），菜可以无限期保存，但每天最多出售 $m$ 个菜，问最大总收益。 为第 $t$ 天的第 $i$ 种蔬菜建立点 $(t,i)$。建边 $S\rightarrow (t,i)$ ，边权为 $a_i$，容量为当天加入的蔬菜数目。 连边 $(t,i)\rightarrow (t+1,i)$ ，容量不限，表示可以将蔬菜留到下一天。 为第 $t$ 天建立一个点表示出售，记为 $[t]$ 。建边 $[t]\rightarrow T$ ，容量为 $m$。 建边 $(t,i)\rightarrow[t]$ ，容量不限。 在菜 $i$ **第一次出现**的时间，从 $S\rightarrow (t,i)$ 中分出一个流量（特殊菜），边权改为 $a_i+s_i$ ，表示出售奖励。 （不难发现，任意一种没有卖掉“特殊菜”情况都可以转化为卖掉“特殊菜”的情况而增加收益，算法一定不会错过奖励） 然后求解最大费用任意流。 - $\small\blacksquare$ **模拟费用流** : 获得性质 & 贪心算法 首先观察建图 :  只有源边有权值，其余边的权值均为 $0$。 考虑使用 “**增量-最大费用任意流**” 模型。 时间倒流后，原来限制只能在前 $1\sim p$ 天（一个前缀）出售，现在变为在一个前缀不能出售，之后才能出售。 **从后向前**依次加入每一天的出售点（这样才能符合原来的时间顺序），观察会新形成怎样的“源汇路”或“环” :  图 $\rm I$ : 未加入出售点时的图。此时图中即没有源汇路也没有环，无需处理。 图 $\rm II$ : 红色部分为新加入的点和边，边的方向是给定的。黑色部分为之前的点和边，边的方向并不确定。 图 $\rm III$ : 三种新的源汇路。具体意义无需关心。 图 $\rm IV$ : 一种新的环。和上一题类似，该方案不如单走一个源汇路，可以排除。 图 $\rm V$ : 一种新的环。注意到不和 S 相连的边均无权，故该环不可能是负环，可以排除。 综上，可能的更新操作中，**所有 S 的出边不会退流**。 因此，我们的决策实际上是非常简单的。形式化地，在**未经时光倒流的原问题**中，前 $p$ 天售卖蔬菜的最优方案，是在前 $p-1$ 售卖蔬菜的最优方案的超集。 有了这个性质，考虑先求出前 $p$ 天的最优方案，然后推出 $1\sim p-1$ 天的方案。 若前 $p$ 天的最优方案为蔬菜集合 $S$ ，则 $S$ 中的所有蔬菜的过期日期都 $\geq p$。 对于第 $p'$ 天，只需保留其中最贵的 $p'*m$ （可能不足）棵，不难发现这是合法的，且是所有合法子集中最优的。 那么将 $S$ 排序就容易得到最终答案。 至于如何求出前 $p$ 天的最优方案，则需设计另一种模拟费用流。 现在已经没有时序的限制，我们可以按照任意顺序处理费用流图。  （我们将思路回到时光倒流后的形式） 图 $\rm I$ : 红色部分为新加入的点和边，黑色部分为之前的点和边。 图 $\rm II$ : 一种可能的源汇路，对应将今天加入的菜直接卖掉。 图 $\rm III$ : 一种可能的源汇路，对应将之前存下的菜卖掉。 图 $\rm IV,V$ : 两种环。和上文类似，可以排除。 在同一种菜中，出售那颗的获益都是一样的，故使用堆维护各种菜即可。当售空时，则从堆中取出。 当加入菜时，若原来这种菜售空，则将其加入堆。这需要维护售空且有持续输入的菜的集合。 （还有一点关于 $s$ 的小细节，不难处理） 复杂度 $O(nm\log n)$。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #define pb push_back #define Pr pair<int,int> #define mp make_pair #define fir first #define sec second #define ll long long #define MaxN 100500 using namespace std; int a[MaxN],s[MaxN],tot[MaxN],d[MaxN],c[MaxN]; int n,lim,m,t[MaxN],tim; ll ans[MaxN*10]; vector<int> g[MaxN]; int st[MaxN],tn; priority_queue<Pr> q; int main() { scanf("%d%d%d",&n,&lim,&m); for (int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i],&s[i],&tot[i],&d[i]); for (int i=1;i<=m;i++){ scanf("%d",&t[i]); tim=max(tim,t[i]); } for (int i=1;i<=n;i++) if (!d[i])g[tim].pb(i); else g[min((tot[i]+d[i]-1)/d[i],tim)].pb(i); for (int t=tim;t;t--){ for (int i=0;i<g[t].size();i++) st[++tn]=g[t][i]; for (int i=1;i<=tn;i++){ int k=st[i]; q.push(mp(!c[k] ? a[k]+s[k] : a[k],k)); }tn=0; int cnt=lim; while(cnt){ if (q.empty())break; int i=q.top().sec; if (!c[i]){ c[i]=1;cnt--; q.pop(); if (tot[i]-d[i]*(t-1)>1)q.push(mp(a[i],i)); else if (d[i])st[++tn]=i; }else { int cnt2=min(tot[i]-d[i]*(t-1)-c[i],cnt); c[i]+=cnt2;cnt-=cnt2; if (tot[i]-d[i]*(t-1)==c[i]) {q.pop();if (d[i])st[++tn]=i;} } } } tn=0; for (int i=1;i<=n;i++){ if (c[i])ans[++tn]=a[i]+s[i]; for (int j=2;j<=c[i];j++)ans[++tn]=a[i]; }sort(ans+1,ans+tn+1);reverse(ans+1,ans+tn+1); for (int i=1;i<=tn;i++)ans[i]+=ans[i-1]; for (int i=1;i<=m;i++) printf("%lld\n",ans[min(tn,t[i]*lim)]); return 0; } ```