最大独立集的求法

.

这个剪枝还挺不错的。$cnt_i$表示$i$到$n$的答案，然后就可以通过它来剪枝了。

bool dfs(int x, int now)
{
    for (int i = x + 1; i <= n; i++)
    {
        if (cnt[i] + now <= ans) return 0;
        if (mp[x][i])
        {
            bool tf = 0;
            for (int j = 0; j < now; j++)
                if (!mp[i][sta[j]])
                {
                    tf = 1;
                    break;
                }
            if (!tf)
            {
                sta[now] = i;
                if (dfs(i, now + 1)) return 1;
            }
        }
    }
    if (now > ans)
    {
        ans = now;
        return 1;
    }
    return 0;
}
void wk
{
    for (int i = n; i > 0; i--)
    {
        sta[0] = i;
        dfs(i, 1);
        cnt[i] = ans;
    }
}