自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:44:49，当前版本为作者最后更新于2023-02-07 15:19:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$n - k$ 的最大独立集唯一对应 $k$ 的点覆盖集。

忽略重边。

对于度数大于 $k$ 的点，若其没有被选择，则与其相连的所有点均被选择，与大小为 $k$ 矛盾。因此，度数大于 $k$ 的点一定被选择。

进一步地，因为接下来每次选择时，覆盖的边数均不超过 $k$，所以当未被覆盖的边数大于 $k ^ 2$ 时，无解。

因为 $k$ 很小，考虑爆搜。

$\mathcal{O}(k ^ 2)$ 找到任意一条未被覆盖的边，选择覆盖其左端点或右端点，至多进行 $k$ 次这样的操作。若当前所有边均被覆盖，设点覆盖集大小为 $c$，则答案加上 $\binom {n - c} {k - c}$。

看似很简单，但是这样会算重：在 $\binom {n - c} {k - c}$ 种方案中，选到我们关注的某条边的另一个端点时，可能与在该分支选择该端点的方案重复。

为避免这种情况，我们需要在找到一条边时，同时确定其两端是否在最终点覆盖集中，也就是除了被选进点覆盖集，一个点还有可能被钦定不可以选进覆盖集。

因为一条边的两端不可能同时不在点覆盖集中，所以只有以下情况：

• 两端均在点覆盖集，大小加 $2$；
• 一端在点覆盖集，另一端不在，两种情况大小均加 $1$。

复杂度递推式为 $\mathcal{T}(k) = 2\mathcal{T}(k - 1) + \mathcal{T}(k - 2)$，但是跑不满（找到一条边的某端钦定不在点覆盖集中时，另一端必须在点覆盖集中）。

时间复杂度 $\mathcal{O}(\mathcal{T}(k) k ^ 2 + m\log m)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int mod = 998244353;
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}
int fc[N], ifc[N];
int bin(int n, int m) {return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;}
int n, m, k, ans;
int u[N], v[N], ban[N];
set<int> e[N];
vector<int> buc;
void dfs(int rest, int cur) {
  if(cur > k) return;
  int e = -1;
  for(auto it : buc)
    if(ban[u[it]] != 1 && ban[v[it]] != 1) {
      e = it;
      break;
    }
  if(e == -1) {
    ans = (ans + bin(rest, k - cur)) % mod;
    return;
  }
  int &x = ban[u[e]], &y = ban[v[e]];
  if(x == 2 && y == 2) return;
  if(x == 2 && y == 0) y = 1, dfs(rest - 1, cur + 1), y = 0;
  if(x == 0 && y == 2) x = 1, dfs(rest - 1, cur + 1), x = 0;
  if(x == 0 && y == 0) {
    x = 1, y = 1, dfs(rest - 2, cur + 2);
    x = 1, y = 2, dfs(rest - 2, cur + 1);
    x = 2, y = 1, dfs(rest - 2, cur + 1);
    x = y = 0;
  }
}
int solve() {
  cin >> n >> m >> k, ans = 0;
  for(int i = 1; i <= n; i++) e[i].clear(), ban[i] = 0;
  for(int i = 1; i <= m; i++) {
    cin >> u[i] >> v[i];
    if(e[u[i]].find(v[i]) != e[u[i]].end()) i--, m--;
    e[u[i]].insert(v[i]);
    e[v[i]].insert(u[i]);
  }
  int cnt = 0;
  for(int i = 1; i <= n && cnt <= k; i++)
    if(e[i].size() > k - cnt) {
      ban[i] = 1, cnt++;
      for(int it : e[i]) e[it].erase(i);
    }
  if(cnt > k) return 0;
  buc.clear();
  for(int i = 1; i <= m; i++)
    if(ban[u[i]] != 1 && ban[v[i]] != 1)
      buc.push_back(i);
  if(buc.size() > k * (k - cnt)) return 0;
  dfs(n - cnt, cnt);
  return ans;
}
int main() {
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for(int i = fc[0] = 1; i < N; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  ifc[N - 1] = ksm(fc[N - 1], mod - 2);
  for(int i = N - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
  int T;
  cin >> T;
  while(T--) cout << solve() << "\n";
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}

每次选度数不为 $0$ 的点或其周围所有点可以做到 $\mathcal{T}(k) = 2 ^ k$。