[洛谷 1352,poj 2342]没有上司的舞会

题目链接

https://www.luogu.org/problem/P1352

题解

我们定义状态 \(f(i,0/1)\) 代表以 \(i\) 为根的子树的最优解(第二维的值为 0 代表 \(i\) 不参加舞会的情况,1 代表 \(i\) 参加舞会的情况)

我们可以得到下面两个状态转移方程(其中 \(x\) 为 \(i\) 的子节点):

  • \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\)(上司不参加舞会时,下属可以参加,也可以不参加)
  • \(f(i,1) = \sum f(x,0) + a_i\)(上司参加舞会时,下属都不会参加)

我们可以通过 DFS,在返回上一层时更新当前节点的最优解。

#include <cstdio>
#include <algorithm>
using namespace std;
struct edge
{
 int v,next;
}e[6005];
int head[6005],n,cnt,f[6005][2],ans,is_h[6005],vis[6005];
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void calc(int k)
{
 vis[k]=1;
 for(int i=head[k];i;i=e[i].next)
 {
  if(vis[e[i].v])continue;
  calc(e[i].v);
  f[k][1]+=f[e[i].v][0];
  f[k][0]+=max(f[e[i].v][0],f[e[i].v][1]);
 }
 return;
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&f[i][1]);
 for(int i=1;i<n;i++)
 {
  int l,k;
  scanf("%d%d",&l,&k);
  is_h[l]=1;
  addedge(k,l);
 }
 for(int i=1;i<=n;i++)
  if(!is_h[i])
  {
   calc(i);
   printf("%d",max(f[i][1],f[i][0]));
   return 0;
  }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注