题解 P3125 【[USACO15OPEN]Bessie的生日自助餐Bessie's…】

Night_Aurora · 2017-09-09 17:38:57 · 题解

原题中的挑剔虽然增加了理解难度，但降低了这个题的编写难度

设DPM[i]表示由i这个点出发，能达到的最多的饱食度

那么很明显DPM[i]=i的质量

DPM[i]=max(DPM[i],DPM[wi]-Dist[wi][i]+i的质量),其中wi质量>i质量

Dist[wi][i]表示从i到wi的最短路长度

只需要设定一个DFS来记忆花搜索，每次搜一个点时SPFA一遍然后再用上面的DP方程就行

复杂度O(kNE)\rightarrow O(10kN^2)

代码

#include <stdio.h>
#include <string.h>
#include <queue>
int N,E;
int Get[1100];
int EHead[1100],ENext[21000],ETo[21000];
int DPM[1100],Elt;
bool DPV[1100];
int Dist[1100][1100];
int Vis[1100][1100];
int SVis[1100];
std::queue<int> Qe;
void SPFA(int sp,int*Dist,int*Vis)
{
    int wi,wt,wl,we;
    Qe.push(sp);
    Dist[sp]=0;
    Vis[sp]=1;
    while(!Qe.empty())
    {
        wi=Qe.front();Qe.pop();
        wl=Dist[wi];
        SVis[wi]=0;
        for(we=EHead[wi];we;we=ENext[we])
            if(!Vis[wt=ETo[we]]||Dist[wt]>wl+E)
            {
                Dist[wt]=wl+E;
                if(!SVis[wt])
                    Qe.push(wt);
                SVis[wt]=Vis[wt]=1;
            }
    }
}
int max(int a,int b)
{return a>b?a:b;}
void DFS(int p)
{
    DPV[p]=1;
    int wi;
    DPM[p]=Get[p];
    SPFA(p,Dist[p],Vis[p]);
    for(wi=1;wi<=N;++wi)
        if(Get[wi]>Get[p])
            if(Vis[p][wi])
            {
                if(!DPV[wi])
                    DFS(wi);
                DPM[p]=max(DPM[p],Get[p]+DPM[wi]-Dist[p][wi]);
            }
}
void AddEdge(int Fr,int To)
{
    ++Elt;
    ENext[Elt]=EHead[Fr];
    ETo[Elt]=To;
    EHead[Fr]=Elt;
}
int main()
{
    scanf("%d %d",&N,&E);
    int wi,wib,t;
    for(wi=1;wi<=N;++wi)
    {
        scanf("%d %d",Get+wi,&wib);
        while(wib--)
        {
            scanf("%d",&t);
            AddEdge(wi,t);
        }
    }
    int mx=0;
    for(wi=1;wi<=N;++wi)
    {
        if(!DPV[wi])
            DFS(wi);
        mx=max(mx,DPM[wi]);
    }
    printf("%d\n",mx);
    return 0;
}