P3125 [USACO15OPEN]Bessie's Birthday Buffet S题解
iterator_it
·
·
题解
BFS 基础题，建议降黄
题意简述：
有 n 片草地，每篇草地与一些草地相邻，奶牛一开始的能量为 0，走到相邻的草地需要花费 e 点能量。
但是贝西很挑剔，每次吃的草的美味程度必须严格大于上一次吃的草。
BFS 可以让我们求出第 i 块草地到第 j 块草地需要多少能量，所以我们可以列出以下转移方程：
dp_j-d_{i,j} \times e + a_i
其中：d_{i,j} 表示从 i 到 j 需要的单位时间，\times e 代表了所需要的能量。
接下来，我们要解决题目的特殊条件，非常简单，在 `BFS` 之前把 $a$ 数组排序以下，`BFS` 的时候只往后面搜索，就可以满足条件。
因为要排序，不能直接使用 $a$ 数组的下标，所以 $a$ 数组应该是结构体类型，里面有他的序号和美味值。
## 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,e,vis[maxn][maxn],d[maxn][maxn],dp[maxn];
struct Node{
int k,v;//k为序号，v是美味值
}a[maxn];
vector<int>g[maxn];
void bfs(int b){
queue<int>q;
q.push(b);
vis[b][b]=1;
d[b][b]=0;
while(q.size()){
int f = q.f();
q.pop();
for(int i=0;i<g[f].size();i++){
int t=g[f][i];
if(!vis[b][t]){
vis[b][t]=1;
d[b][t]=d[b][f]+1;
q.push(t);
}
}
}
}
bool cmp(Node A,Node B){
return A.v<B.v;//按美味值排序
}
int main(){
cin>>n>>e;
for(int i=1;i<=n;i++){
cin>>a[i].v;
a[i].k=i;
int t;
cin>>t;
for(int j=1;j<=t;j++){
int x;
cin>>x;
g[i].push_back(x);
}
}
for(int i=1;i<=n;i++)
bfs(i);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
dp[i]=a[i].v;
for(int j=1;j<i;j++){
if(vis[a[i].k][a[j].k])
dp[i]=max(dp[i],dp[j]-d[a[i].k][a[j].k]*e+a[i].v);
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i]);
cout<<ans;
return 0;
}
```