题解：P13358 [GDCPC 2024] 小班课

xxxxxzy · 2026-09-07 10:13:44 · 题解

题解几把在说啥。首先进行按优先级顺序增广的二分图匹配（匈牙利算法），我们猜测答案就是最大匹配，首先记 i 的匹配点为 p_i。我们下面证明，一定存在一个匹配顺序，使得 i 恰好匹配到 p_i：

• 在这种情况下，我们在某个时刻能够选择 i 当且仅当 i 在 p_i 之前优先级的目标点被全部占满。
• 如果点 i 存在某个比 p_i 优先级更高的目标点的点被 j 匹配了，那么我们给 j \to i 连一条边，能构造出方案当且仅当这张图没有环，是一张 DAG。
• 考虑反证，如果这张图有环，记环上的点是 x_1 \sim x_k，对应匹配的点是 y_1 \sim y_k，那么在原二分图上一定形如 y_1 \to x_1 \to y_2 \to x_2 \to ... \to y_k \to x_k \to y_1，其中 y_i \to x_i 是匹配边，那么我们在加入 x_k 时，首先会遍历到 y_1，而此时 y_1 \to y_k 构成一条增广路，那么 x_k 会直接和 y_1 匹配，所以不会出现环。

那么每次找一个合法的学生就做完了，时间复杂度 O(n^3)。

::::info[代码]

const i32 N = 505;
i32 T, n, m, ans, b[N], s[N], a[N][N], mat[N], cnt[N], num[N][N], vis[N];
fv init() { ans = 0, mem(vis, 0), mem(mat, 0), mem(num, 0); }
fn bool dfs(i32 now, i32 tag) {
  if (vis[now] == tag) return 0;
  vis[now] = tag;
  rep (i, 1, s[now]) {
    i32 v = a[now][i];
    rep (j, 1, b[v]) {
      if (!num[v][j] || dfs(num[v][j], tag)) {
        mat[now] = v;
        num[v][j] = now;
        return 1;
      }
    }
  }
  return 0;
}
fv sol() {
  cin >> n >> m;
  init();
  rep (i, 1, m) cin >> b[i];
  rep (i, 1, n) {
    cin >> s[i];
    rep (j, 1, s[i]) cin >> a[i][j];
  }
  rep (i, 1, n) if (dfs(i, i)) ans++;
  cout << ans << '\n';
  rep (i, 1, n) cnt[mat[i]]++;
  mem(vis, 0);
  rep (i, 1, n) {
    rep (j, 1, n) {
      if (vis[j]) continue;
      bool flag = 1;
      i32 k = 1;
      while (a[j][k] != mat[j]) {
        if (cnt[a[j][k]]) { flag = 0; break; }
        ++k;
      }
      if (flag) {
        vis[j] = 1;
        cout << j << " ";
        cnt[mat[j]]--;
        break;
      }
    }
  }
  cout << "\n";
}
int main() {
  IOS;
  cin >> T;
  while (T--) sol();
}

::::