P3354 [IOI2005] Riv 河流
模拟退火0pts求调

#include<bits/stdc++.h>
using namespace std;
#define DEL 0.995

int f[120],v[120],d[120],h[120],ans[120],leaf[120];
long long answer;
long long cnt = 0, n, k, t;
long long que[120],riv[120],vis[120];
long long cal(int *s)
{
	long long ansns=0;
	for(int i=0;i<=n;i++)
		riv[i]=vis[i]=que[i]=0;
	int tail=0,head=0;
	for(int i=1;i<=cnt;i++)
		que[++tail]=leaf[i],vis[leaf[i]]=1;
	while(head<tail)
	{
		head++;
		int x = que[head];
		if(f[x]!=-1&&!vis[f[x]])
			que[++tail]=f[x],vis[f[x]]=1;
		if(!s[x])
			riv[f[x]]+=riv[x]+v[x]*d[x];
		else ansns+=riv[x];
	}
	return ansns;
}

void SA()
{
	int s[120];
	for(int i=1;i<=n;i++)s[i]=ans[i];
	t=3000;
	while(t>1e-15)
	{
		int x=rand()%n+1,y=rand()%k+1;
		while(s[x])
			x=rand()%n+1;
		int bb=0,zz;
		for(zz=1;zz<=n&&bb!=y;zz++)
			if(s[zz])bb++; 
		s[x]=1;
		s[zz-1]=0;
		long long now=cal(s);
		long long del=now-answer;
		if(del<0){
			ans[x]=1;ans[zz-1]=0;answer=now;
		}else if(exp(del/t)*RAND_MAX<=rand()) s[x]=0,s[zz]=1;
		t*=DEL;
	}
}

void work()
{
	ans[0]=1;for(int i=1;i<=k;i++)ans[i]=1;
	answer=cal(ans);
	SA();SA();SA();SA();SA();
}

int main()
{
	srand(1e9+7);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>v[i]>>f[i]>>d[i];
	for(int i=1;i<=n;i++)
		h[f[i]]=1;
	for(int i=1;i<=n;i++)
		if(!h[i])leaf[++cnt]=i;
	f[0]=-1;
	work();
	cout<<answer;
	return 0;
}