题解【P3826 [NOI2017] 蔬菜】

· · 题解

更严谨的正确性分析。

更自然的非启发式思路。（然而也有点难想）

更强的扩展性。（然而也没做过几个题）

更多的草稿纸。

广告 ： 模拟费用流小记 （建议阅读）

题意 : 有 n 种蔬菜，第 i 种蔬菜单价是 a_i，初始时数量为 c_i，若不出售，每天有 x_i 份会变质。初次出售第 i 种蔬菜可以获得 s_i 的奖励。

每天可以卖掉 m 个未变质的蔬菜。有 k 个询问，每次问在 1\sim p 天出售蔬菜能够获得的最大收益。

首先解释一下题意。

同种蔬菜中，每棵蔬菜都有自己独立的变质时间，在不出售的情况下，效果是每天有 x_i 份会变质。但可以出售这些较快变质的菜，保留那些较慢变质的菜。

也可以理解为，将蔬菜再按照过期时间分类为不同类别的菜。

考虑时间倒流，问题变为 : 每天都会加入一些菜（原来会变质的菜），菜可以无限期保存，但每天最多出售 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 ，表示出售奖励。

（不难发现，任意一种没有卖掉“特殊菜”情况都可以转化为卖掉“特殊菜”的情况而增加收益，算法一定不会错过奖励）

然后求解最大费用任意流。

首先观察建图 :

只有源边有权值，其余边的权值均为 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)。

#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;
}