BZOJ 1040: [ZJOI2008]骑士（基环树dp）-白红宇

BZOJ 1040: [ZJOI2008]骑士（基环树dp）

阅读量：4980 次

发布时间：2019-06-12

本文共 2007 字，大约阅读时间需要 6 分钟。

题意：

思路：

这是基环树，因为每个人只会有一个厌恶的人，所以每个节点只会有一个父亲节点，但是根节点也是有父亲节点的，所以在树中肯定是存在一个环的，只要删除该环中的任意一条边，那么就能将该图变成一颗树。

如果是树的话，那就很简单了，d[u][0/1] dp求解即可。

现在假设删除的边是e，两端的节点分别是u，v，首先对u为根的树作一次dp，最后取d[u][0]（v取不取都无所谓），不能取d[u][1]（因为此时可能也取了v）。但是这样的话没有考虑选u的情况，所以再对v为根的树作一次dp，最后取d[v][0]。两者取大者即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
          6 using namespace std; 7 const int maxn = 1000000+5; 8 typedef long long ll; 9 10 int n,tot=0,edgeID,edgeLeft,edgeRight;11 int head[maxn],vis[maxn];12 ll val[maxn], d[maxn][2];13 14 struct node15 {16     int v,next;17 }e[2*maxn];18 19 void addEdge(int u,int v)20 {21     e[tot].v = v;22     e[tot].next = head[u];23     head[u] = tot++;24 }25 26 void dfs(int u, int fa)27 {28     vis[u] = 1;29     for(int i=head[u];i!=-1;i=e[i].next)30     {31         int v = e[i].v;32         if(v == fa)  continue;33         if(!vis[v])  dfs(v,u);34         else   //找到了环35         {36             edgeID = i;  //记录边和两端顶点37             edgeLeft = u;38             edgeRight = v;39         }40     }41 }42 43 ll dp(int u, int fa)44 {45     d[u][0] = 0, d[u][1] = val[u];46     for(int i=head[u];i!=-1;i=e[i].next)47     {48         int v = e[i].v;49         if(v==fa)  continue;50         if(i==edgeID || i==(edgeID^1))  continue;  //正向边和反向边51         dp(v,u);52         d[u][0] += max(d[v][0],d[v][1]);53         d[u][1] += d[v][0];54     }55     return d[u][0];56 }57 58 int main()59 {60     //freopen("in.txt","r",stdin);61     memset(head,-1,sizeof(head));62     scanf("%d",&n);63     for(int i=1;i<=n;i++)64     {65         int x;66         scanf("%lld%d",&val[i],&x);67         addEdge(i,x);68         addEdge(x,i);69     }70     ll ans = 0;71     for(int i=1;i<=n;i++)72     {73         if(vis[i])  continue;74         dfs(i,-1);75         ans += max(dp(edgeLeft,-1),dp(edgeRight,-1));76     }77     printf("%lld\n",ans);78     return 0;79 }

转载于:https://www.cnblogs.com/zyb993963526/p/8047818.html

你可能感兴趣的文章