BZOJ 5126 [Lydsy12月赛]自动售货机

题目大意

给你一个坏了的自动售货机，如果$i$有库存的话，买一件物品$i$会花掉i的钱得到一件物品$f_i$并使得$f_i$的库存减少1，每件物品卖给超市可获得$m_i$，求最大总获利。

首先如果一个东西可以赚钱那就找售货机价格最小的能得到它的卖出它，易知卖到所有东西只剩一个之前不会改变整个系统的形态。

之后剩下的东西是——每个点都有一条边与其相连的——基环树森林。

之后就可以基环树DP啦~对于树的部分，答案就是每个点的入边获利的最大值；对于环的部分考虑删掉一条边使得其成为一条链。枚举删掉的链就可以O(1)求出来了。

细节贼多。其实也不多我判断买那个最优的时候判断错了= = （题解代码后有DataMaker代码）

#include <queue>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define R register
#define N 100010
int f[N],p[N],m[N],s[N],v[N],r[N],c[N],t[N];
int to[N<<1],nxt[N<<1],head[N],tot;
long long ans;
queue<int>q;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
	R int ret=0;R char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
inline void AE(R int X,R int Y) {to[++tot]=Y,c[Y]++,nxt[tot]=head[X],head[X]=tot;}
int main()
{
	R int n=RI();
	p[0]=1<<30;
	for(R int i=1;i<=n;++i)
	{
		f[i]=RI(),p[i]=RI(),m[i]=RI(),s[i]=RI();
		if(p[i]<p[r[f[i]]]) r[f[i]]=i;
		AE(i,f[i]);
	}
	for(R int i=1;i<=n;++i) if(r[i]&&m[i]-p[r[i]]>0)
		t[i]=m[i]-p[r[i]],ans+=1ll*(s[i]-1)*t[i],s[i]=1;
	for(R int i=1;i<=n;++i) if(!c[i]) q.push(i);
	while(!q.empty())
	{
		R int tmp=q.front();
		q.pop();
		ans+=v[tmp];
		for(R int i=head[tmp];i;i=nxt[i])
		{
			v[to[i]]=max(v[to[i]],m[to[i]]-p[tmp]),c[to[i]]--;
			if(!c[to[i]]) q.push(to[i]);
		}
	}
	for(R int i=1;i<=n;++i) if(f[i]==i) ans+=t[i],c[i]=0;
	for(R int i=1;i<=n;++i) if(c[i])
	{
		q.push(i);
		c[i]--;
		R int res=1<<30;
		while(!q.empty())
		{
			int tmp=q.front();
			q.pop();
			for(R int i=head[tmp];i;i=nxt[i])
			{
				ans+=max(v[to[i]],m[to[i]]-p[tmp]),c[to[i]]--;
				res=min(res,max(0,m[to[i]]-p[tmp]-v[to[i]]));
				if(!c[to[i]]) q.push(to[i]);
			}
		}
		ans-=res;
	}
	printf("%lld\n",ans);
	return 0;
}

DataMaker

from random import randint
f = open("dp.in", "w")
n = 30
MAXN = 100
f.write("%d\n" % n)
for i in range(n): f.write("%d %d %d %d\n" % (randint(1,n), randint(1,MAXN), randint(1,MAXN), randint(1,MAXN)))