P3450 Zos-Sophie

· · 题解

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;
}