【bzoj1040】骑士[ZJOI2008]（树形dp）

　　题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1040

　　这道题，很明显根据仇恨关系构造出的图形是一堆环套树。如果是普通的树，就可以马上裸树形dp了，于是我们先解决这个环的问题。所以要先把环找出来。

　　找出环后，假如断掉一条环边，环套树就变成了普通的树，而我们可以直接对这棵树进行dp，但是要控制被断掉的边的两端不被选择。

　　对断边形成的树进行dp的时候，我们的dp方程是这样表示的：f[i][0/1]表示结点i不选/选。

　　假设断掉的两条边两端的结点是x和y，然后我们可以发现：当以x为根时，f[x][0]包含了不选x，选/不选y的情况；而当以y为根时，f[y][0]包含了不选y，选/不选x的情况。把这两种情况取个max，刚好就绕过了既选x，又选y的情况。

　　然后把每棵环套树的答案加起来即可。

　　PS：QAQ……细节调了快两个小时……

　　代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define ll long long

#define min(a,b) (a<b?a:b)

#define max(a,b) (a>b?a:b)

ll read()

{

    ll tmp=; char f=,c=getchar();

    while(c<''||''<c){if(c=='-')f=-; c=getchar();}

    while(''<=c&&c<=''){tmp=tmp*+c-''; c=getchar();}

    return tmp*f;

}

using namespace std;

int fir[],to[],ne[];

int a[];

bool vis[];

ll f[][];

int n,root,del,tot=;

ll ans=;

void add(int x,int y){to[tot]=y; ne[tot]=fir[x]; fir[x]=tot++;}

void dfs(int now,int pa)

{

    vis[now]=;

    for(int i=fir[now];i>=;i=ne[i])

        if(i!=(pa^)){

            if(vis[to[i]]){

                root=to[i]; del=i^; continue;

            }

            dfs(to[i],i);

        }

}

void dp(int now,int pa)

{

    f[now][]=a[now]; f[now][]=;

    for(int i=fir[now];i>=;i=ne[i])

        if(i!=(pa^)&&i!=del&&i!=(del^)){

            dp(to[i],i);

            f[now][]+=f[to[i]][];

            f[now][]+=max(f[to[i]][],f[to[i]][]);

        }

}

void work()

{

    dfs(root,-);

    dp(root,-);

    ll tmp=f[root][];

    dp(to[del],-);

    ans+=max(tmp,f[to[del]][]);

}

int main()

{

    n=read();

    for(int i=;i<=n;i++)fir[i]=-;

    for(int i=;i<=n;i++){

        int x=read(),y=read();

        a[i]=x; add(i,y); add(y,i);

    }

    for(int i=;i<=n;i++)

        if(!vis[i])root=i,work();

    printf("%lld",ans);

}

bzoj1040

　　总结：遇到环套树的题，或者先断掉一条环边处理树，再把边的情况考虑进去；或者先处理环上的子树，再考虑整个环。

巴特西

【bzoj1040】骑士[ZJOI2008]（树形dp）

最新文章

热门文章