BZOJ 2060: [Usaco2010 Nov]Visiting Cows – [树形DP]


题目传送门(BZOJ)
>原文链接<

题解 :

这个东西好像是叫最大独立集?

状态 :F[i]代表选ii子树拜访数量,G[i]表示不选i的最大拜访数量。

转移 :F[i] = 1+\sum G[to[i]] , G[i] = \sum\max(G[to[i]], F[to[i]])

最后答案是\max(F[1], G[1])

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 50001;
int n;
int head[N],to[N<<1],next[N<<1],cnt;
int f[N],g[N];
void add_edge(int a,int b) {
    to[++cnt]=b;
    next[cnt]=head[a];
    head[a]=cnt;

    to[++cnt]=a;
    next[cnt]=head[b];
    head[b]=cnt;

}
void dfs(int p,int fa) {
    for(int i=head[p];i;i=next[i]) {
        if(to[i]!=fa) {
            dfs(to[i],p);
            f[p]+=g[to[i]];
            g[p]+=max(g[to[i]],f[to[i]]);
        }
    }
    f[p]++;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i

发表评论

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