自动搬运

查看原文

来自洛谷，原作者为

	yaoxi **

搬运于2025-08-24 21:49:06，当前版本为作者最后更新于2022-09-23 11:41:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3450 Zos-Sophie

更好的阅读体验

简要题意: 给出一个 $n$ 个点 $m$ 条边的无向图 $G$，问是否存在顶点个数不小于 $k$ 的独立集，如果存在，找出顶点个数最多的独立集。

数据规模: $2 \le n \le 10^6,\, 1 \le m \le 3\times10^6,\, n-10 \le k \le n$。

题解: 图的最大独立集是个 NP 完全问题，但是数据给定了 $n - 10 \le k \le n$，那么首先显然有 $O(n^{10})$ 的多项式复杂度算法，即暴力枚举删去的点。为了表述的方便，下文中令 $l=n-k$，即最多能删去的点数；同时令 $d_u$ 表示点 $u$ 的度数。

考虑图上最大独立集的对偶问题，即图上最小点覆盖（用最少的点覆盖每一条边）。如此以来，问题转化为考虑用哪些点去覆盖所有的边。为了防止意义上的混淆，定义集合 $V'$ 表示最小点覆盖中选出的点集。

算法 $\text{I}$ : 我们先任取一个度数 $> 0$ 的点 $u$，并考察是否 $u \in V'$。假设 $u \in V'$ 成立，则将 $u$ 及其相邻的边删去；否则根据最小点覆盖的性质，与 $u$ 相邻的其他点必有 $v \in V'$，将与 $u$ 相邻的所有点 $v$ 及 $v$ 周围的边删去即可。并递归上述操作 $l$ 次，每次操作后判断边集是否为空。

下面分析上述算法的时间复杂度。注意到每次操作必须删除至少 $1$ 个点，所以递归的总层数不超过 $l$。同时显然每层有 $2$ 种决策，所以递归次数为 $O(2^l)$。而由于判断边集是否为空需要 $O(n+m)$ 判断或维护，所以时间复杂度为 $O((n+m)2^l)$，虽然无法通过此题，但相比 $O(n^{10})$ 的方法有了很高的优化空间。

算法 $\text{II}$ : 考虑度数 $> l$ 的点，显然这些点必须 $\in V'$，否则将无法在 $l$ 次内覆盖其连出的所有边。那么可以在一开始删去这些点，如果这些点的数量 $> l$，直接输出 NIE。考察剩余度数 $> 0$ 的点的数量，观察到：

引理 $\text{I}$ : 如果图 $G$ 的所有点度数均 $\le l$，且最小点覆盖大小 $< l'$，则 $G$ 中的边数不超过 $l \times l'$，度数 $> 0$ 的点数不超过 $2\times l \times l'$。

证明显然，考虑每个点覆盖集合中的点都覆盖了 $l$ 条边，即可确定点数和边数的上界。

因此，在删完度数 $> l$ 的点并忽略孤立点后，若残余图 $G'$ 中的点数仍然 $> 2\times l \times l'$，就直接输出 NIE。这样图 $G'$ 的大小就有了明确的上界，即 $|V_{G'}|, |E_{G'}| \le 2l^2$。若在该图中暴力选择 $l$ 个点判断，复杂度为 $O(\binom{2l^2}{l} \times l^2)$。结合算法 $\text{I}$，便能够在 $O(n+m+l^22^l)$ 的时间复杂度内解决此题。

代码有较多的细节，以及一些地方需要精细实现以保证复杂度。

注：随机化算法也能够通过此题，可以见 Claris 的博客。

spj 待修，如果管理员来审这篇题解了请看这个帖子。

代码:

using ll = long long;
const int N = 1e6 + 10, M = 3e6 + 10;
int n, m, k, sz, mp[N], deg[N];
bool del[N];
set<int> g[N], rec[N];
vector<int> ans;
pair<int, int> edg[M];
set<pair<int, int>> st;
bool check() {
    vector<int> res;
    for (int i = 1; i <= sz; ++i) {
        if (!g[mp[i]].empty()) return false;
        if (del[mp[i]]) res.push_back(mp[i]);
    }
    if (res.size() < ans.size() || (res.size() == ans.size() && res > ans))
        ans = res;
    return true;
}
bool dfs(int p, int cnt) {
    if (cnt > k) return false;
    if (check()) return true;
    while (p <= sz && g[mp[p]].empty()) ++p;
    if (p > sz) return false;
    bool ret = false;
    int u = mp[p]; set<int> adj = g[u];
    for (auto v : adj) g[v].erase(u);
    swap(g[u], rec[u]), del[u] = true;
    ret |= dfs(p + 1, cnt + 1);
    swap(g[u], rec[u]), del[u] = false;
    for (auto v : adj) g[v].insert(u);
    for (auto v : adj)
        for (auto w : g[v]) g[w].erase(v);
    for (auto v : adj)
        swap(g[v], rec[v]), del[v] = true;
    ret |= dfs(p + 1, cnt + adj.size());
    for (auto v : adj)
        swap(g[v], rec[v]), del[v] = false;
    for (auto v : adj)
        for (auto w : g[v]) g[w].insert(v);
    return ret;
}
signed main() {
    read(n), read(k), read(m), k = n - k;
    for (int i = 1, u, v; i <= m; ++i)
        read(u), read(v), edg[i] = minmax(u, v);
    sort(edg + 1, edg + m + 1);
    m = unique(edg + 1, edg + m + 1) - edg - 1;
    for (int i = 1, u, v; i <= m; ++i)
        tie(u, v) = edg[i], ++deg[u], ++deg[v];
    for (int i = 1; i <= n; ++i)
        if (deg[i] > k) --k, del[i] = true;
    fill(deg + 1, deg + n + 1, 0);
    for (int i = 1, u, v; i <= m; ++i) {
        tie(u, v) = edg[i];
        if (!del[u] && !del[v])
            g[u].insert(v), g[v].insert(u);
    }
    for (int i = 1; i <= n; ++i)
        if (!g[i].empty()) mp[++sz] = i;
    ans.resize(sz);
    if (sz > 2 * k * k || !dfs(1, 0)) return puts("NIE"), 0;
    for (auto p : ans) del[p] = true;
    ans.clear();
    for (int i = 1; i <= n; ++i) if (!del[i]) ans.push_back(i);
    write(ans.size()), putchar('\n');
    for (int i = 0; i < (int)ans.size(); ++i)
        write(ans[i]), putchar(" \n"[i == (int)ans.size() - 1]);
    return 0;
}