首页
登录 | 注册

[UOJ 28][IOI 2014]Friend(DP)

题目链接

http://uoj.ac/problem/28

题目大意

有一个点带权的无向图,最开始只有点0,随后点1至点n1依次加入,点i加入时,会有一个已经加入的点hosti,它会在点i和其他一些点进行连边,连边方式有以下三种:
1. I方式:只将ihosti连边
2. M方式:只将ihosti
3. W方式:将ihosti
求最终的图的最大点独立集。

思路

整个问题可以倒过来看,相当于从最后一次操作开始,对每次操作的边(u,v)进行[删u/v]的操作,并保证最终没有两个点是联通的。
建立一个新的树,每个点ihosti,这个树有I、M、W三种树边。
这样就相当于在一棵树上做最大点独立集,可以用树上DP解决。
不妨设f[i]=iig[i]=ii,这里之前的含义是按照操作顺序已经完成了的那些操作。
对于I类边(hosti,i)而言,就是一般的树上最大点独立集的求法(如没有上司的舞会),DP方程为f[hosti]=f[hosti]+g[i],g[hosti]=g[hosti]+max{f[i],g[i]}
[UOJ 28][IOI 2014]Friend(DP)

对于M类边(hosti,i)而言,如上图,如果之前选了hosti,那么i现在可选也可不选,如果之前不选hosti,说明那一次有一个i保留了下来,成为了hosti的邻居,这次i需要与i连边,而i已经选了了,那么i就不能选。因此f[hosti]=max(f[hosti]+max(f[i],g[i]),g[hosti]+f[i]),g[hosti]=g[hosti]+g[i]

对于W类边(hosti,i)而言,如果在之前某次操作选了hosti,那么这次i就可以,如果在之前都没选过hosti,这次可以选hosti,i就不能选。
f[hosti]=max{f[hosti]+g[i],g[hosti]+f[i]},g[hosti]=g[hosti]+g[i]

代码

#include "friend.h"

#define MAXV 110000

int max(int a,int b)
{
    if(a>b) return a;
    return b;
}

int f[MAXV],g[MAXV]; //f[i]=可以选点i,子树能得到的最大权值,g[i]=不选点i,子树能得到的最大权值

// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[])
{
    for(int i=0;i<n;i++) f[i]=confidence[i];
    for(int i=n-1;i>0;i--) //对第i个点进行操作
    {
        int fa=host[i]; //i在新建的树中的父亲是fa
        if(!protocol[i]) //I连法,i与其父亲连
        {
            f[fa]+=g[i];
            g[fa]+=max(f[i],g[i]);
        }
        else if(protocol[i]==1) //M连法,i与其父亲的邻居连
        {
            f[fa]=max(f[fa]+max(f[i],g[i]),g[fa]+f[i]);
            g[fa]+=g[i];
        }
        else //W连法,i与其父亲以及其父亲的邻居连
        {
            f[fa]=max(f[fa]+g[i],g[fa]+f[i]);
            g[fa]+=g[i];
        }
    }
    return max(f[0],g[0]);
}



2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号