【BZOJ】1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

【算法】基环树DP

【题意】给定若干有向基环树，每个点能走的最远路径长度。

【题解】

参考：【BZOJ1589】Trick or Treat on the Farm 基环树裸DP by 空灰冰魂

考虑DAG上DP，令f[x]表示点x开始能到达的最远长度，则f[x]=f[y]+1,x--->y。

环套树最重要的操作就是找环，可以用tarjan缩点，也可以用简单的找环写。

找环：在vis上给访问过的点标号，从每个未访问过的点开始遍历，用栈存储路上的点，遇到vis标号相同的点说明找到环，然后弹出。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int nex[maxn],s[maxn],n,f[maxn],top,vis[maxn];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&nex[i]);

    for(int i=;i<=n;i++)if(!vis[i]){

        int j=i;

        top=;

        while(!vis[j]){

            vis[j]=i;

            s[++top]=j;

            j=nex[j];

        }

        if(vis[j]==i){

            int cnt=;

            while(s[top-cnt+]!=j)cnt++;

            for(int k=;k<=cnt;k++)f[s[top-k+]]=cnt;

            top-=cnt;

        }

        int k=;

        while(top>)f[s[top--]]=f[j]+(++k);

    }

    for(int i=;i<=n;i++)printf("%d\n",f[i]);

    return ;

}

巴特西

【BZOJ】1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

最新文章

热门文章