BZOJ-4316 小C的独立集(仙人掌DP)

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4316

题目大意

求一个仙人掌上的最大独立集

解题思路

仙人掌有若干种 DP,比如最大独立集和直径。
最大独立集比较简单,只需要 DFS 时,树边按照树上独立集的方式转移,环上用一个 f(i,0..1,0..1) 的简单 DP 去转移即可。

代码

#include <bits/stdc++.h>
const int mod=1e9+7;
const int maxn=1e6+100;
using namespace std;
typedef long long ll;
int n,m,tot;
int dp[maxn][2],low[maxn],dfn[maxn],fa[maxn];
vector<int>mp[maxn];
void cal(int rt,int now) {
    int t=now,s0=0,s1=0;
    while(now!=rt) {
        int tmp=s0;
        s0=max(s0,s1)+dp[now][0];
        s1=tmp+max(dp[now][1],dp[now][0]);
        now=fa[now];
    }
    dp[rt][0]+=max(s0,s1);
    //强制不选第一个点
    s0=-0x3f3f3f3f;
    s1=0;
    now=t;
    while(now!=rt) {
        int tmp=s0;
        s0=max(s0,s1)+dp[now][0];
        s1=tmp+max(dp[now][1],dp[now][0]);
        now=fa[now];
    }
    dp[rt][1]+=s0;
}
void dfs(int now) {
    dp[now][1]=1;
    dfn[now]=low[now]=++tot;
    for(int v:mp[now]) {
        if(v==fa[now])
            continue;
        if(!dfn[v]) {
            fa[v]=now;
            dfs(v);
            low[now]=min(low[now],low[v]);

        } else
            low[now]=min(low[now],dfn[v]);
        if(dfn[now]<low[v]) { //正常树边
            dp[now][0]+=max(dp[v][0],dp[v][1]);
            dp[now][1]+=dp[v][0];
        }
    }
    for(int v:mp[now]) {
        if(fa[v]!=now&&dfn[v]>dfn[now])
            cal(now,v);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int u,v;
    for(int i=0; i<m; i++) {
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs(1);
    cout<<max(dp[1][0],dp[1][1])<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注