[ZJOI2008]骑士 DP dfs

题解：

　　观察题面可以很快发现这是一棵基环内向树（然而并没有什么用。。。）

　　再稍微思考一下，假设将这个环中的任意一点设为root，然后去掉root到下面的特殊边（即构成环的那条边），那么就构成了一棵树，并且可以用简单树形DP解决。

　　再考虑加上这条边的限制，设被去掉的这条边是连接root 和 x的，这条边实际上就是限制了在选root的时候不能选x，那么考虑一个暴力的想法。

　　我们先在图中dfs，找到这个环，然后任意指定一点为root，再跑两边树形DP，一遍强制不选root，然后跑普通树形DP。另一遍强制选root，然后跑树形DP加上特判不能选x，最后两种答案取max即可。

　　我这样写可能比较长，别人的做法只要写两遍dfs，我需要3遍（不过后面两个dfs可以复制粘贴）。但实际上是一个思路。别人的做法是dfs找到这个环，然后随便找条环上的边断开，然后强制这条边连接的两个点其中一个不选（其实就和我的写法一样的意思，只不过我是先把这两个点中的一个指定为了root）

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 1000100

 #define ac 2000100

 #define LL long long

 int n, m, root;

 int s[AC], p[AC], deep[AC];

 LL f[AC][], g[AC][], ans;//存下每个点的厌恶对象以方便判断

 int Head[AC], date[ac], Next[ac], tot;

 bool z[AC], vis[AC], book[AC], flag;

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void add(int f, int w)

 {

     date[++tot] = w, Next[tot] = Head[f], Head[f] = tot;

     date[++tot] = f, Next[tot] = Head[w], Head[w] = tot;

 }

 void pre()

 {

     n = read();

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

     {

         s[i] = read(), p[i] = read();

         add(i, p[i]);

     }

     deep[] = ;

 }

 void dfs1(int x)//找到反向边的那个点定为root

 {

     z[x] = true;

     int now;

     //if(root) return ;

     for(R i = Head[x]; i; i = Next[i])

     {

         now = date[i];

         if(z[now] && deep[now] +  != deep[x]) root = x;

         if(z[now] && p[now] == x && p[x] == now) root = x, flag = true;//特殊情况

         //if(root) return ;

         if(z[now]) continue;

         deep[now] = deep[x] + ;

         dfs1(now);

     }

 }

 void dfs2(int x)//强制选root

 {

     int now;

     vis[x] = true;

     f[x][] = s[x];//初始化

     for(R i = Head[x]; i; i = Next[i])

     {

         now = date[i];

         if(vis[now]) continue;

         if(now == p[x] && x == root && !flag) continue;

         dfs2(now);//忽略这条边,如果是特殊情况则不能忽略，因为是重边,一旦忽略将忽略2条

         f[x][] += f[now][];

         f[x][] += max(f[now][], f[now][]);

     }

     if(x == p[root]) f[x][] = f[x][];

 }

 void dfs3(int x)//强制不选root

 {

     int now;

     g[x][] = s[x];

     book[x] = true;

     for(R i = Head[x]; i; i = Next[i])

     {

         now = date[i];

         if(book[now]) continue;

         if(now == p[x] && x == root && !flag) continue;

         dfs3(now);

         g[x][] += g[now][];

         g[x][] += max(g[now][], g[now][]);

     }

 }

 void work()

 {

     for(R i = ; i <= n; i ++)//因为本来就不一定联通，所以要跑多次

         if(!z[i])

         {

             dfs1(i);

             dfs2(root);

             dfs3(root);

             ans += max(f[root][], g[root][]);

         }

     printf("%lld\n", ans);

 }

 int main()

 {

 //    freopen("in.in", "r", stdin);

     pre();

     work();

 //    fclose(stdin);

     return ;

 }

巴特西

[ZJOI2008]骑士 DP dfs

最新文章

热门文章