P3125 [USACO15OPEN]Bessie's Birthday Buffet S题解

· · 题解

大佬们用什么 SPFA 和 DP，我这个蒟蒻根本看不懂，既然看不懂，就来水一篇简单易懂的 BFS + DP 的题解吧！

题意简化：

有 n 片草地，每篇草地与一些草地相邻，奶牛一开始的能量为 0，走到相邻的草地需要花费 e 点能量。

之所以这题使用 BFS，是因为它的每一个点不是与其他点相通的，并且只会吃比之前吃的草更好吃，即能量更多的草。

所以我们只需要用 BFS 遍历一遍，记录每片草地能从哪些草地过来，这是 BFS 要做的事情。

接下来，就来到 DP 的部分了。

首先给出递推式：

f_i=\max(f_i,f_j-\mathit{d}_{{a_i.id},{a_j.id}} \times e+a_i.v)

先解释一下式子中变量的意思，f_i 代表在第 i 片草坪结束的最大能量，d 数组表示两片草坪中间需要走过多少草地，a_i.id 表示第 i 片草坪的编号，a_j.id 也同理，a_i.v 表示在第 i 片草地能吃到的能量值。

然后来解释一下这个式子，通过推导，可以发现从第 i 片到第 j 片需要 d[i][j]*e 的能量值，于是这个式子就被我们推导出来了。

完整代码：

#include<bits/stdc++.h>
using namespace std;
int n,e,vis[1010][1010],d[1010][1010],f[1010];
struct cow{
    int id,v;
}a[1010];
vector<int>g[1010];
void bfs(int b){
    queue<int>q;
    q.push(b);
    vis[b][b]=1;
    d[b][b]=0;
    while(q.size()){
        int front = q.front();
        q.pop();
        for(int i=0;i<g[front].size();i++){
            int t=g[front][i];
            if(!vis[b][t]){
                vis[b][t]=1;
                d[b][t]=d[b][front]+1;
                q.push(t);
            }
        }
    }
}
bool cmp(cow A,cow B){
    return A.v<B.v;
}
int main(){
    cin>>n>>e;
    for(int i=1;i<=n;i++){
        cin>>a[i].v;
        a[i].id=i;
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            int temp;
            cin>>temp;
            g[i].push_back(temp);
        }
    }
    for(int i=1;i<=n;i++)
        bfs(i);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        f[i]=a[i].v;
        for(int j=1;j<i;j++){
            if(vis[a[i].id][a[j].id])
                f[i]=max(f[i],f[j]-d[a[i].id][a[j].id]*e+a[i].v);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}