最大加权独立集问题

Dear 丶 2022-09-04 07:49 195阅读 0赞

若加 权图 Ｇ＝ｆＶ，目的顶点集  的子集  中的任何 顶点  之间都不相邻 ，则称  为 图 Ｇ的独立集 ，顶点个数最多的独  立集称为最大独立 集。各顶点权 重之和最大 的独立集称为图  Ｇ的最大加权独立集 。如图 １所示 ，顶点集合 （４，３，１）是该图  的一个独立集， 且是最 大独立集 ，但不是最大加权独立集 。  顶点集合（５，２）是独立集，且是最大加权独立集 。最大加权独  立集 问题 已被证明为是个 ＮＰ完全问题。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyODgxOTA_size_16_color_FFFFFF_t_70][]

一棵树，每个点有一个权值，选择一个权值最大的无父子节点点集。

关键词：树的最大”权值“独立集

f\[i\]\[0\]：以i为根的子树不选根节点最大权值，

f\[i\]\[1\]：以i为根的子树选根节点最大权值

f\[u\]\[1\]+=f\[v\]\[0\];

f\[u\]\[0\]+=max(f\[v\]\[1\],f\[v\]\[0\]);

注：

1.若所有点的权值都大于0，则树的最大”权值“独立集也是极大点独立集，即任选两个点，一定有且仅有一个在该集合中。若存在点的权值小于0，则不一定成立。

变题：选择一个无祖先与后代节点的最大权值点集

f\[u\]:以i为根的子树的最大权值

f\[u\]=max\{ w\[u\],sum\{f\[v\]\},v是u的孩子 \} 两个选择：当前节点/后代，两个选择互斥

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    #include<algorithm>
    #include<map>
    #include<vector>
    #include<queue>
    #define ll long long
    #define sf scanf
    #define pf printf
    #define maxn 10000
    #define inf 0x3f3f3f
    #define INF 1ll<<60
    #define mem(a,b) memset(a,b,sizeof(a))
    #define lowbit(x) x&(-x)
    using namespace std;
     
     
    int n;
    int a[maxn],du[maxn];
     
    struct Edge{
        int to,next;
    }edge[maxn];
    int head[maxn],tot;
    int f[maxn][2];//f[u][0]：子树不含u的最大欢乐值 f[u][1]：子树含u的最大欢乐值
     
    void add(int a,int b){
        edge[tot].to=b,edge[tot].next=head[a],head[a]=tot++;
    }
     
    void dp(int u){
        f[u][1]=a[u],f[u][0]=0;
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            dp(v);
            f[u][1]+=f[v][0];
            f[u][0]+=max(f[v][1],f[v][0]);
        }
    }
     
    int main(){
        //freopen("a.txt","r",stdin);
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        mem(head,-1),mem(du,0),mem(f,0),tot=0;
        for(int i=1;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add(b,a);
            du[a]++;
        }
        for(int i=1;i<=n;i++)
            if(!du[i]) {dp(i);printf("%d\n",max(f[i][0],f[i][1]));break;}
    }

原文链接：https://blog.csdn.net/u013514182/article/details/42202021

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyODgxOTA_size_16_color_FFFFFF_t_70]: /images/20220829/9693aa3ff6334a36a2a2c8e808f43e00.png