BZOJ4316 小C的独立集

BZOJ

分析

我们在 $\mathrm{tarjan}$ 的同时跑 $\mathrm{dp}$ 。

设 $f[i][0/1]$ 表示 $i$ 子树中, $i$ 选/不选的最大独立集大小。

如果一条边是桥,那么和树上独立集一样的转移。

否则,这条边在环上,那么暂时先不转移。


假设我们现在正在 $u$ 点,$v$ 点已经访问过了,那么 $v$ 是这个环的顶端, $u$ 是这个环的底端。

这时我们可以通过跳父节点找到这个环。我们对这个环单独做一遍 $\mathrm{dp}$ ,然后把答案累加到环的顶端去。

考虑怎么计算环上的答案。我们从底端跳父节点到顶端,同时 $\mathrm{dp}$ 。

设 $f_0$ 表示当前节点不选的最大独立集大小, $f_1$ 表示当前节点选的最大独立集大小。

如果顶端不选的话,那么底端无所谓选不选,把 $f_0$ 和 $f_1$ 的初值设为 $0$ 转移即可。

如果顶端选的话,那么底端一定不能选,把 $f_0$ 的初值设为 $1$ 、 $f_1$ 的初值设为 $-\infty$ 转移即可。


具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000,M=60000;

int n,m;

struct Edge { int v,nxt; } e[M<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int dfn[N],low[N],tim=0;
int fa[N],f[N][2];

inline void dp(int u,int v) { //环的DP
    int f0=0,f1=0;
    for (re int i=v;i!=u;i=fa[i]) {
        int x=f0+f[i][0],y=f1+f[i][1];
        f0=max(x,y),f1=x;
    }
    f[u][0]+=f0;
    f0=0,f1=-2e9;
    for (re int i=v;i!=u;i=fa[i]) {
        int x=f0+f[i][0],y=f1+f[i][1];
        f0=max(x,y),f1=x;
    }
    f[u][1]+=f1;
}

inline void tarjan(int u,int pa) {
    dfn[u]=low[u]=++tim;
    fa[u]=pa,f[u][0]=0,f[u][1]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v,u),low[u]=min(low[u],low[v]);
        else if (v!=pa) low[u]=min(low[u],dfn[v]);
        if (low[v]>dfn[u]) f[u][1]+=f[v][0],f[u][0]+=max(f[v][0],f[v][1]);
    }
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (fa[v]!=u&&dfn[u]<dfn[v]) dp(u,v);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    tarjan(1,0);
    printf("%d\n",max(f[1][0],f[1][1]));
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 34 PM

发表评论