【BZOJ4316】小C的独立集（动态规划）

时间：2024-07-30 09:05:44

【BZOJ4316】小C的独立集（动态规划）

题面

BZOJ

题解

考虑树的独立集求法

设\(f[i][0/1]\)表示\(i\)这个点一定不选，以及\(i\)这个点无所谓的最大值

转移\(f[u][0]=\sum f[v][1]\)，\(f[u][1]=\sum f[v][0]\),\(f[u][1]=max(f[u][1],f[u][0])\)

现在放在了仙人掌上，

我们可以看做一棵树加上了若干不相交的返祖边

于是再加上一维\(f[u][0/1][0/1]\)

其中最后一维表示这条边所在的环的最底端的那个点一定不选，或者无所谓

赋初值：\(f[u][1][1]=1\),如果这个点不是所在环的最底端，\(f[u][1][0]=1\)

此时的转移：

1.两个点的底端点相同

这个时候我们先只考虑强制不选底端的转移

那么，\(f[u][1][0]+=f[v][1][1],f[u][1][1]+=f[v][1][0]\)

也就是上面裸的在树上的转移

2.两个点的底端点不同

既然跨越了环，意味着\(u\)就是这个环的底端点，\(v\)是它所在环的顶端点

那么，可以\(u\)选\(v\)不选，因为跨越了环，所以对于\(v\)的底端点选择与否我们是不关心的

而第二维的\(1\)表示的\(u\)无所谓，后面的\(0\)则是强制不选择\(u\)

因此\(f[u][0][0]+=f[v][1][1]\)，\(f[u][1][0]+=f[v][0][0]\)

3.\(v\)的顶端点不是\(u\)

意味着不用担心底端点产生的影响

所以\(f[u][0][1]+=f[v][1][1]\)，\(f[u][1][1]+=f[v][0][1]\)

4.\(v\)的顶端点是\(u\)

此时要考虑底端点的贡献了

此时当前\(u\)不选，那就没有什么问题\(f[u][0][1]+=f[v][1][1]\)

当前\(u\)选择，强制不能选择底端点\(f[u][1][1]+=f[v][0][0]\)

好了，这样就讨论完了四种转移，然后就可以啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 55555

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next;}e[MAX*3];

int h[MAX],cnt=1,n,m;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int dep[MAX],fa[MAX];

int tp[MAX],un[MAX];

void dfs(int u,int ff)

{

	fa[u]=ff;dep[u]=dep[ff]+1;

	for(int i=h[u];i;i=e[i].next)

		if(!dep[e[i].v])dfs(e[i].v,u);

}

void jump(int u,int v){int x=v;while(x!=u)tp[x]=u,un[x]=v,x=fa[x];}

int f0[MAX],f1[MAX],g0[MAX],g1[MAX];

void dp(int u)

{

	f1[u]=1;

	if(u!=un[u])g1[u]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;if(dep[u]+1!=dep[v])continue;

		dp(v);

		if(un[u]!=un[v])g0[u]+=f1[v],g1[u]+=g0[v];

		else g0[u]+=g1[v],g1[u]+=g0[v];

		if(tp[v]!=u)f0[u]+=f1[v],f1[u]+=f0[v];

		else f0[u]+=f1[v],f1[u]+=g0[v];

	}

	f1[u]=max(f1[u],f0[u]);

	g1[u]=max(g1[u],g0[u]);

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	dfs(1,0);

	for(int u=1;u<=n;++u)

		for(int i=h[u];i;i=e[i].next)

			if(dep[u]<dep[e[i].v]&&fa[e[i].v]!=u)

				jump(u,e[i].v);

	dp(1);

	printf("%d\n",f1[1]);

	return 0;

}

相关文章