题解：P10779 BZOJ4316 小 C 的独立集

· · 题解

P10779 BZOJ4316 小 C 的独立集

感谢管理大大的审核

虽然在圆方树专题中，但我们没有必要把圆方树建出来...

AD：\large 博客喵~

题意

给出一个仙人掌图，求最大独立集

就像是没有上司的舞会超级加倍

没有做过的可以先去康康~

分析

显然树形DP，但是是在仙人掌图上。

至于啥是仙人掌图嘛~

感性的李姐一下就是一棵树塞几个基环且强连通。

引用某dalao的一张图就是：

由于有环，不难想到 Tarjan，所以我们考虑在 Tarjan 的过程中求解。

我们设 f[i][1/0] 为 i 节点 选/不选 的最优答案，

当一条边是树边的时候，正常DP。

否则暂时不转移。

当我们做完当前点，发现它是一个环的最顶端的时候，我们需要重新对这个环计算一遍答案。

从这个环的最底端开始往上跳，每次合并一次答案。

维护两个变量 f0,f1，表示当前点选或者不选的答案。

考虑分讨：

没了。

Code

#include<bits/stdc++.h>
#define 我永远喜欢 return
#define 伊蕾娜 0;
using namespace std;
#define int long long
#define rd read()
#define pii pair<int,int>
#define mkp make_pair
#define psb push_back
inline int read(){
    int f=1,x=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    return f*x;
}
const int N=1e5+100;
const int inf=0x7fffffff7fffffff;

int n,m,cnt,f[N][2],fa[N];
vector<int> G[N],T[N*2];
int dfn[N],low[N],num;

void dp(int x,int y){
    int g0=0,g1=0,f0=0,f1=0;
    for(int i=y;i!=x;i=fa[i]){
        g0=f0+f[i][0],g1=f1+f[i][1];
        f0=max(g0,g1),f1=g0;
    }
    f[x][0]+=f0;

    f0=0,f1=-inf;
    for(int i=y;i!=x;i=fa[i]){
        g0=f0+f[i][0],g1=f1+f[i][1];
        f0=max(g0,g1),f1=g0;
    }
    f[x][1]+=f1;
}

void tarjan(int x,int ff){
    fa[x]=ff;
    low[x]=dfn[x]=++num;
    f[x][1]=1,f[x][0]=0;
    for(auto to:G[x]){
        if(!dfn[to]){
            tarjan(to,x);
            low[x]=min(low[x],low[to]);
        }else if(to!=ff){
            low[x]=min(low[x],dfn[to]);
        }
        if(low[to]>dfn[x]){
            f[x][1]+=f[to][0],f[x][0]+=max(f[to][0],f[to][1]);
        }
    }
    for(auto to:G[x]){
        if(fa[to]!=x&&dfn[x]<dfn[to]){
            dp(x,to);
        }
    }
}

signed main(){
    n=rd,m=rd;
    for(int i=1;i<=m;i++){
        int x=rd,y=rd;
        G[x].psb(y);
        G[y].psb(x);
    }
    tarjan(1,0);
    printf("%lld",max(f[1][0],f[1][1]));
    我永远喜欢 伊蕾娜
}