蒟蒻的小窝

蒟蒻的小窝

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

posted on 2020-08-21 20:53:30 | under 题解 |

对于每一片草地,如果吃了这个草地的草,那么再要吃的话只能吃质量比这块地更高的,那么果断对土地按照质量从低到高排序,然后刷 $n$ 次 $BFS$,刷出每个点到另一点的最短路,那么对于 $i$ 这个点,如果要吃的话,就从 $1----i-1$ 之前找一个最大值,然后 $i$ 的值就是 $i$ 位置草的质量和之前最大值 $+i$ 位置草的质量 $-e*i----$ 最大值的最短路。最后在 $1----n$ 刷一趟最大值就ok了。(代码有坑)

Code:

#include<bits/stdc++.h>
using namespace std;
struct ZS{
    int v,id;
    bool operator <(const ZS b)const{return v<b.v;}
}a[10005];
int n,e,tot,ans;
int lnk[1005],w[1005],v[1005],q[100005],nxt[20005],son[20005];
int dis[1005][1005];
bool vis[1005];
void make(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
void BFS(int x){
    int hed=0,til=1;vis[x]=1;q[til]=x;
    while(hed<=til)
        for(int i=lnk[q[++hed]];i;i=nxt[i])if(!vis[son[i]]){
            dis[x][son[i]]=dis[x][q[hed]]+1;
            q[++til]=son[i];vis[son[i]]=1;
    }
    memset(vis,0,sizeof vis);
}
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
int main()
    freopen("buffet.in","r",stdin);
    freopen("buffet.out","w",stdout);
    n=read();e=read();
    for(int i=1;i<=n;i++){
        a[i].v=read();a[i].id=i;
        w[i]=v[i]=a[i].v;
        int x=read();
        for(int j=1;j<=x;j++){
            int y=read();
            make(i,y);make(y,i);
        }
    }
    for(int i=1;i<=n;i++)BFS(i);
    sort(a+1,a+1+n);
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)if(dis[a[i].id][a[j].id])w[a[j].id]=max(w[a[j].id],w[a[i].id]+v[a[j].id]-e*dis[a[i].id][a[j].id]);
    for(int i=1;i<=n;i++)ans=max(ans,w[i]);
    printf("%d\n",ans);
    return 0;
}