luogu3826 [NOI2017]蔬菜

[NOI2017]蔬菜

太神了写不来

一眼看出来是个网络流（费用流），口胡一个建图（勿轻信，未实践）：对每一天用一个节点来表示，卖什么菜则用连边表示，对于当前的蔬菜，源点向这种蔬菜未完全变质的天连边，容量为在这一天变质的蔬菜量，费用为(a_i)，特别的对于(s_i)，我们在最后一天单独拆一条边，流量为1，费用为(a_i+s_i)，同时每一天向前一天连一条容量为(inf),费用为(0)的边，表示最迟在这一天必须被卖出去的蔬菜可以放在前面被卖出，最后每一天向汇点连容量为(m)，费用为(0)的边，这样应该可以获得(56-60pts)

那么如何优化呢？我们可以模拟这个费用流的过程。注意到这样一个重要的性质：在前(i-1)天卖出去蔬菜一定是前(i)天卖出去的蔬菜的子集，于是在上面的费用流中由(S)连出去的那一部分是不会发生退流操作的，于是我们可以用一个堆来维护每一种蔬菜当前的价值，每次从取出一个最大的元素，看它是否能在一个合法的天数之前被卖掉，这个可以用堆+并查集维护

于是就做完了QAQ，这个模拟费用流还是比较好写的，关键点是注意到不会发生退流操作

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define int long long
typedef long long ll;
typedef long double db;
const int N=100000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8

struct node{
    int val,id;
};
bool operator <(node p,node q) {return p.val<q.val;}
priority_queue<node> q;
struct vegetable{
    int a,c,x,s;
}a[100100];
int n,m,qcnt,fa[100100],cnt[100100];
ll ans[100100];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int find(int x)
{
    if (fa[x]==x) return fa[x];
    fa[x]=find(fa[x]);
    return fa[x];
}

signed main()
{
    n=read();m=read();qcnt=read();
    rep(i,1,n)
    {
        a[i].a=read();a[i].s=read();a[i].c=read();a[i].x=read();
        if (a[i].c) q.push((node){a[i].s+a[i].a,i});
    }
    rep(i,1,N) fa[i]=i;
    ll sum=0;
    rep(i,1,N)
    {
        int j;
        for (j=1;j<=m && !q.empty();j++)
        {
            node now=q.top();q.pop();
            int lat;
            if (!a[now.id].x) lat=N;
            else lat=min(N,(a[now.id].c-1)/a[now.id].x+1);
            int pos=find(lat);
            //cout << pos << " " << lat << endl;
            if (!pos) {j--;continue;}cnt[pos]++;
            if (cnt[pos]==m) fa[pos]=find(pos-1);
            sum+=now.val;a[now.id].c--;
            if (a[now.id].c) q.push((node){a[now.id].a,now.id});
        }
        //cout << endl;
        ans[i]=sum;
    }
    while (qcnt--) printf("%lld
",ans[read()]);
    return 0;
}