Description

\(n\) 种物品，每种有 \(a_i\) 个，能够 \(C_i\)，买入 \(D_i\) 卖出。由于一些原因，买 \(i\) 实际上会弹出 \(f_i\)。

如果第 \(i\) 种物品被买完了，就不能购买（得不到 \(f_i\)）；即使给了钱买了 \(i\)，但是 \(f_i\) 没货了，也不会出货。

最大化利润。

Solution

如果将所有 \((i,f_i)\) 连上，那就是一个内向基环树森林。边的含义就是一种购买关系，对于 \(u\to v\) 必须 \(u\) 还有货才能买到 \(v\) 。边权就是利润 \(D_{f_i}-C_i\)，负权肯定不会要。所以直接不连边。基环树就可能会退化成一些普通的树（此时所有边权值均为正）。容易发现对于一棵树来说，只有叶子节点不能被卖到，其他的通过一定顺序购买一定能买到，而且一定会选择入边边权最大的来购买。考虑基环树的情况，统计每个点入边边权的最大值和次大值。对于基环树上非环上节点，除了叶子一定能被买完。对于环上的点，如果存在一个点的入边最大值不在环上，那么可以先把其他的点买完，再买这个点，这样就能全部买到；如果最大值都在环上产生，那么看存不存在非环的支链，让该支链所连的点少贡献一条环上的边，这样其他的就可以买完，对于这种情况我们要选择增量最小的；对于单纯的环，一定买不完，只能舍弃一个权最小的边。

然后tm场上判环写错了，又不给点大样例

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘) flag=0;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

const int N=1e5+7;

struct E{
    int next,to;
}e[N];

struct Node{
    int val,pre;
}t[2][N];

bool vis[N],ins[N],tag[N];
int f[N],C[N],D[N],a[N];
int sta[N],top=0,cnt=0,tot=0,head[N];
vector<int> ci[N];

inline void add(int id,int to){
//    printf("Link %d %d\n",id,to);
    e[++cnt]=(E){head[id],to};
    head[id]=cnt;
}

void dfs(int u){
    sta[++top]=u,vis[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(ins[v]){
            int y; tot++;
            do{
                tag[y=sta[top--]]=1;
                ci[tot].push_back(y);
            }while(y!=v);
        }else if(!vis[v]) ins[u]=1,dfs(v),ins[u]=0;
    }
    top--;
}

int main(){
    freopen("goods.in","r",stdin);
    freopen("goods.out","w",stdout);
    int n=read();
    for(int i=1;i<=n;i++)
        f[i]=read(),C[i]=read(),D[i]=read(),a[i]=read();
    for(int i=1;i<=n;i++)
        if(D[f[i]]>C[i]) add(i,f[i]);
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
    for(int i=1;i<=n;i++){
        int w=D[f[i]]-C[i],v=f[i]; if(w<=0) continue;
        if(t[0][v].val<w||(t[0][v].val==w&&!tag[i]))
            t[1][v]=t[0][v],t[0][v]=(Node){w,i};
        else if(t[1][v].val<w||(t[1][v].val==w&&!tag[i]))
            t[1][v]=(Node){w,i};
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        if(!tag[i]) ans+=1ll*a[i]*t[0][i].val;
    for(int i=1;i<=tot;i++){
        if(ci[i].size()==1){
            int v=ci[i][0];
            ans+=1ll*a[v]*t[0][v].val;
            continue;
        }
        bool flag=0;
        for(unsigned int j=0;j<ci[i].size();j++)
            if(!tag[t[0][ci[i][j]].pre]){flag=1;break;}
        for(unsigned int j=0;j<ci[i].size();j++)
            ans+=1ll*t[0][ci[i][j]].val*a[ci[i][j]];
        if(!flag){
            int delta=-1e9;
            for(unsigned int j=0;j<ci[i].size();j++){
                int v=ci[i][j];
                if(!t[1][v].pre) continue;
                if(!tag[t[1][v].pre])
                    delta=max(delta,t[1][v].val-t[0][v].val);
            }
            if(delta!=-1e9){ans+=delta;continue;}
            delta=1e9;
            for(unsigned int j=0;j<ci[i].size();j++)
                delta=min(delta,t[0][ci[i][j]].val);
            ans-=delta;
        }
    }
    printf("%lld",ans);
}

ZYB和售货机