题解：P10779 BZOJ4316 小 C 的独立集

Felix72 · 2025-12-05 16:51:19 · 题解

简要题意：求仙人掌最大独立集。

是一道可以 1 \text{🐟} 2 吃的题。

法一：圆方树上 DP

主观难度评价（参考 LCA 的题目难度向度，[1, 7] 代表从红到黑）：

先建圆方树，然后我们发现这是一个圆方树上 经典问题，多出来的限制是环上的相邻点不能都选。

这是一个 \max+ 矩阵转移的模型。对于圆点，设 f_{p, 0/1} 表示该点选不选时子树内的最大贡献。对于每个方点，先不考虑其父亲节点 fa，然后对剩下的一条链进行转移即可。无限制的最大贡献给到 f_{fa, 0}，两端都不选的最大贡献给到 f_{fa, 1}。

代码如下：

/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 50010;
int n, m; vector < int > tr[N];

struct node {int blank, occu;}; node f[N * 2];
node operator + (node u, node v) {return {u.blank + v.blank, u.occu + v.occu};}
struct Matrix
{
    int h, w, s[2][2];
    inline void reset(int n, int m)
    {
        h = n, w = m;
        memset(s, -0x3f, sizeof(s));
    }
    inline void unit(int n)
    {
        reset(n, n);
        for(int i = 0; i < n; ++i) s[i][i] = 0;
    }
    inline void debug()
    {
        cerr << "debug : " << h << " x " << w << '\n';
        for(int i = 0; i < h; ++i)
        {
            for(int j = 0; j < w; ++j)
                cerr << s[i][j] << " ";
            cerr << '\n';
        }
    }
};
inline Matrix Export(node u)
{
    Matrix ret; ret.reset(2, 2);
    ret.s[0][0] = u.blank;
    ret.s[1][0] = u.blank;
    ret.s[0][1] = u.occu;
    return ret;
}
Matrix operator * (Matrix u, Matrix v)
{
    Matrix res; res.reset(u.h, v.w);
    for(int i = 0; i < u.h; ++i)
        for(int j = 0; j < u.w; ++j)
            for(int k = 0; k < v.w; ++k)
                res.s[i][k] = max(res.s[i][k], u.s[i][j] + v.s[j][k]);
    return res;
}

// 建圆方树 
deque < int > bft[N * 2]; int fa[N * 2];
inline void init(int pos, int prt)
{
    fa[pos] = prt;
    for(int to : bft[pos])
    {
        if(to == prt) continue;
        init(to, pos);
    }
}
inline void treedp(int pos, int prt)
{
    if(pos <= n)
    {
        f[pos] = {0, 1};
        for(int to : bft[pos])
        {
            if(to == prt) continue;
            treedp(to, pos);
        }
//      cerr << pos << " : " << f[pos].blank << " " << f[pos].occu << '\n';
    }
    else
    {
        Matrix current; current.unit(2);
        for(int i = 1; i < (int)bft[pos].size(); ++i)
        {
            int to = bft[pos][i];
            treedp(to, pos);
            current = current * Export(f[to]);
        }
        Matrix dp[2]; for(int i = 0; i <= 1; ++i) dp[i].reset(1, 2);
        dp[0].s[0][0] = 0, dp[1].s[0][1] = 0;
        dp[0] = dp[0] * current, dp[1] = dp[1] * current;
        f[fa[pos]] = f[fa[pos]] + (node){max(dp[0].s[0][0], dp[0].s[0][1]), dp[1].s[0][0]};
    }
}
int dfn[N], low[N], sign, bcc, sta[N], top;
inline bool cmp(int x, int y) {return dfn[x] < dfn[y];}
inline void tarjan(int pos)
{
    dfn[pos] = low[pos] = ++sign; sta[++top] = pos;
    for(int to : tr[pos])
    {
        if(!dfn[to])
        {
            tarjan(to);
            low[pos] = min(low[pos], low[to]);
            if(low[to] == dfn[pos])
            {
                ++bcc; sta[top + 1] = 0;
                while(sta[top + 1] != to)
                {
                    bft[sta[top]].push_back(n + bcc);
                    bft[n + bcc].push_back(sta[top]);
                    --top;
                }
                bft[pos].push_back(n + bcc);
                bft[n + bcc].push_back(pos);
            }
        }
        else low[pos] = min(low[pos], dfn[to]);
    }
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1, x, y; i <= m; ++i)
    {
        cin >> x >> y;
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    tarjan(1);
    init(1, 0); // 预处理出圆方树上每个节点的父亲 
    for(int i = n + 1; i <= n + bcc; ++i)
    {
        sort(bft[i].begin(), bft[i].end(), cmp);
        while(bft[i].front() != fa[i])
        {
            bft[i].push_back(bft[i].front());
            bft[i].pop_front();
        }
    }
    treedp(1, 0);
    cout << max(f[1].blank, f[1].occu) << '\n';
    return 0;
}
/*

*/

法二：广义串并联图上 DP

主观难度评价（参考 LCA 的题目难度向度，[1, 7] 代表从红到黑）：

直接对于每条边 (u, v) 设状态 dp_{0/1, 0/1} 表示 u/v 选不选时不考虑 u, v 贡献的最大独立集。初始时所有 dp 都是 0。

原图是广义串并联图，因此我们考虑缩图。我们发现这个 DP 状态可以把并联或串联的两条边缩成一条等价的边，则直接应用广义串并联图方法即可。

代码可以参考其他题解。