[USACO15OPEN]Bessie's Birthday Buffet S 题解

本文主要是介绍[USACO15OPEN]Bessie's Birthday Buffet S 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

为了庆祝奶牛Bessie的生日，Farmer John给了她一块最好的牧场，让她自由的享用。

牧场上一共有 \(N\) 块草地 \((1≤N≤1000)\)，编号为\(1...N\)，每块草地上牧草的质量都不同。

如果Bessie吃掉的草地上牧草质量为 \(Q\)，她可以获得 \(Q\) 单位的能量。

每块草地最多和\(10\)块草地有相连的道路，在相连的两个草地之间走动需要消耗E单位的能量 \((1≤E≤1,000,000)\)。

Bessie可以从任意一块草地开始吃草，并且想要在获得了最多能量的时候停止。

有点遗憾的，Bessie是一头挑食的奶牛，一旦她吃过了一定质量的牧草，她就不会再吃相同或更低质量的牧草！但是她仍然很愿意路过某些草地，而不吃它们。实际上，她发现路过一块高质量的草地而不吃它，等一下返回再去享用，有时会更有利！

请帮忙计算Bessie能够获得的能量的最大值。

输入格式

1行：包含两个整数 \(N\) 和 \(E\)。

接下来N行：每行描述一块草地，首先两个整数 \(Q\) 和 \(D\)，分别表示草地上牧草的质量（范围1…1,000,000）和相连的草地数量。然后 \(D\)个整数表示相连的草地。

输出格式

输出Bessie能够获得的能量的最大值。

样例输入

5 2
4 1 2
1 3 1 3 4
6 2 2 5
5 2 2 5
2 2 3 4

样例输出

7

读题完毕，我们发现决定答案的因素主要有二

• 奶牛到达不同点的时候的点权和（升序）

• 走路径所花费的精力 \(E\)

起初可能觉得处理升序是最麻烦的点，实则不然，发现点权可以通过从小到大排序解决，处理的问题就在如何快速求出从一点到另一个点花费的精力 \(E\)

点数非常小，暴力解决问题，即\(BFS\)预处理出两点之间的精力

状态 \(F[i]\) 表示到达前 \(i\) 个点时的最大精力，由于提前排序，所以可以看作一个简单的 \(01\) 背包

状态转移方程：\(F[i]=max(F[i],F[i-dis_{i-j}]+w[i])\)

Code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010,M=5e4+10;
int h[N],idx,ne[M],e[M],dis[N][N],n,E,res=-1,f[N];
bool st[N];
struct node {int w,num;}a[M];
bool cmp(node a,node b) {return a.w<b.w;}
void add(int u,int v) {ne[++idx]=h[u],e[idx]=v,h[u]=idx;}
void bfs(int u)
{
	queue<int> q;
	memset(st,0,sizeof st);
	dis[u][u]=0,st[u]=1,q.push(u);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=h[now];~i;i=ne[i])
		{
			int j=e[i];
			if(!st[j])
				st[j]=1,dis[u][j]=dis[u][now]+E,q.push(j);
		}
	}
	return ;
}
signed main()
{
	scanf("%lld%lld",&n,&E);
	memset(h,-1,sizeof h);memset(dis,0x7f,sizeof dis);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%lld%lld",&a[i].w,&x);
		a[i].num=i;
		while(x--)
		{
			int v;
			scanf("%lld",&v);
			add(i,v);
		}
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) bfs(i);
	for(int i=0;i<=n;i++) dis[0][i]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;j++) f[i]=max(f[i],f[j]-dis[a[j].num][a[i].num]+a[i].w);
		res=max(res,f[i]);
	}
	printf("%lld",res);
	return 0;
}

这篇关于[USACO15OPEN]Bessie's Birthday Buffet S 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！