P9170 [省选联考 2023] 填数游戏

· · 题解

P9170 [省选联考 2023] 填数游戏

在 T_{i, 1} 和 T_{i, 2} 之间连边，选择每条边的一端使得选择的点互不相同，则任意连通块满足 |V| \geq |E|，否则无解。

每条边 (u, v) 根据 S_i 有四种状态：什么都不选，只选 u，只选 v，两个都可以选。若 |S_i\cap T_i| = 0，则这条边一定不会产生贡献。若 |S_i\cap T_i| = 1，则 Alice 一定选择交集里的元素。若 |S_i\cap T_i| = 2，则 Alice 可以选择任何一个元素。

对于 \boldsymbol{|V| = |E|}，连通块的形态是基环树。

对于不在环上的边，Bob 只能选叶向端，因此如果一条边的状态是只选叶向端或两个都可以选，则 Alice 一定会让这条边产生贡献。

对于环上的边：

对于 \boldsymbol{|V| = |E| + 1}，连通块的形态是树。

Bob 有 |V| 种策略：不选连通块中的某个点。设 f_i 表示不选 i 的代价，则 Alice 给一条边定向的影响形如给一侧子树的 f 加 1，求 \min f 的最大值。

现在我们只关心未定向的边该如何定向。考虑任意两条未定向的边，设它们分别给 V_1, V_2 的 f 加 1。若 V_1 和 V_2 无交，我们可以把这两条边都反向，将 V_i 变成 V\backslash V_i。这样至少给每个 f 加了 1，一定不劣。

因此，任意两条未定向的边的 V_i 有交，则所有 V_i 的交非空。枚举交集中的某个点 x，则所有未定向的边的方案是确定的：以 x 为根的叶向。这样，对应的 f_i 等于 f_x + mn_{x, i}，其中 mn_{x, i} 表示 x 到 i 的根向边的数量，减去 x 到 i 的叶向边的数量。

直接枚举 x 并计算 f_i，时间复杂度 \mathcal{O}(n ^ 2)。

换根时维护以 x 为根的 f_x，以及 x 子树内所有 i 的 mn_{x, i} 的最小值。需要预处理以初始 x 为根，每个结点 i 子树内所有 u 的 mn_{i, u} 的最小值和次小值。具体细节根据父亲走向子节点时 f 和 mn 的变化讨论一下即可。

时间复杂度 \mathcal{O}(n + m)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool Mbe;
constexpr int N = 1e6 + 5;

int n, m, s1[N], s2[N];
struct edge {
  int to, w, id;
  // w = -1: useless
  // w = 0: choose this
  // w = 1: choose to
  // w = 2: any
};
vector<edge> e[N];

int V, E, vv[N], ve[N], deg[N];
vector<int> c;
void dfs(int id) {
  V++, vv[id] = 1, c.push_back(id);
  for(auto _ : e[id]) {
    int it = _.to;
    if(!ve[_.id]) E++, ve[_.id] = 1;
    if(!vv[it]) dfs(it);
  }
}

namespace Cyc { // ez
  int solve() {
    int ans = 0, on = -1;
    queue<int> q;
    for(int id : c) {
      deg[id] = e[id].size();
      if(deg[id] == 1) q.push(id);
      else on = id;
    }
    while(!q.empty()) { // let's toposort!
      int t = q.front();
      q.pop(), V--;
      for(auto _ : e[t]) {
        int it = _.to;
        if(deg[it] > 1) {
          ans += _.w == 0 || _.w == 2;
          if(--deg[it] == 1) q.push(it);
          else on = it;
        }
      }
    }
    if(V == 1) {
      for(auto _ : e[on]) {
        int it = _.to;
        if(on == it) {
          ans += _.w >= 0;
          break;
        }
      }
    }
    else {
      int c0 = 0, c1 = 0, c2 = 0;
      int cur = on, lst = 0;
      while(V--) {
        for(auto _ : e[cur]) {
          int it = _.to;
          if(deg[it] == 1) continue;
          if(_.id == lst) continue;
          if(_.w == 0) c0++;
          if(_.w == 1) c1++;
          if(_.w == 2) c2++;
          cur = it, lst = _.id;
          break;
        }
      }
      if(c0 > c1) swap(c0, c1);
      if(c0 + c2 <= c1) ans += c0 + c2;
      else ans += (c0 + c1 + c2) / 2;
    }
    return ans;
  }
}

namespace Tree { // 2 hard 4 me
  int f[N], g[N], mn[N], smn[N], gmn[N];
  void dfs1(int id, int ff) {
    f[id] = g[id] = mn[id] = smn[id] = gmn[id] = 0;
    for(auto _ : e[id]) {
      int it = _.to;
      if(it == ff) continue;
      dfs1(it, id);
      f[id] += f[it];
      if(_.w > 0) f[id]++;
      int v = mn[it];
      if(_.w == 0) v++;
      if(_.w > 0) v--;
      if(v < mn[id]) smn[id] = mn[id], mn[id] = v;
      else if(v < smn[id]) smn[id] = v;
    }
  }
  void dfs2(int id, int ff) {
    gmn[id] = min(gmn[id], 0);
    for(auto _ : e[id]) {
      int it = _.to;
      if(it == ff) continue;
      g[it] = g[id] + f[id] - f[it] - (_.w > 0);
      if(_.w == 0 || _.w == 2) g[it]++;
      int v = mn[it];
      if(_.w == 0) v++;
      if(_.w > 0) v--;
      gmn[it] = min(gmn[id], v == mn[id] ? smn[id] : mn[id]);
      if(_.w == 0 || _.w == 2) gmn[it]--;
      if(_.w == 1) gmn[it]++;
      dfs2(it, id);
    }
  }
  int solve() {
    dfs1(c[0], 0), dfs2(c[0], 0);
    int ans = 0;
    for(int id : c) ans = max(ans, f[id] + g[id] + min(mn[id], gmn[id]));
    return ans;
  }
}

void solve() {
  cin >> n >> m;
  for(int i = 1; i <= m; i++) e[i].clear(), vv[i] = 0;
  for(int i = 1; i <= n; i++) {
    ve[i] = 0;
    int sz;
    cin >> sz >> s1[i];
    if(sz == 1) s2[i] = -1;
    else cin >> s2[i];
  }
  for(int i = 1; i <= n; i++) {
    int sz, x, y = -1;
    cin >> sz >> x;
    auto add = [&](int u, int v, int w) {
      e[u].push_back({v, w, i});
    };
    if(sz == 1) {
      if(s1[i] == x || s2[i] == x) add(x, x, 0), add(x, x, 0);
      else add(x, x, -1), add(x, x, -1);
    }
    else {
      cin >> y;
      if(s2[i] == -1) {
        if(s1[i] == x) add(x, y, 0), add(y, x, 1);
        else if(s1[i] == y) add(x, y, 1), add(y, x, 0);
        else add(x, y, -1), add(y, x, -1);
      }
      else {
        if(s1[i] > s2[i]) swap(s1[i], s2[i]);
        if(x > y) swap(x, y);
        if(s1[i] == x && s2[i] == y) add(x, y, 2), add(y, x, 2);
        else if(s1[i] == x || s2[i] == x) add(x, y, 0), add(y, x, 1);
        else if(s1[i] == y || s2[i] == y) add(x, y, 1), add(y, x, 0);
        else add(x, y, -1), add(y, x, -1);
      }
    }
  }

  int ans = 0;
  for(int i = 1; i <= m; i++) {
    if(e[i].empty() || vv[i]) continue;
    V = E = 0, c.clear(), dfs(i);
    if(V < E) return cout << "-1\n", void();
    if(V == E) ans += Cyc::solve();
    else ans += Tree::solve();
  }
  cout << ans << "\n";
}

bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("game.in", "r", stdin);
    FILE* OUT = freopen("game.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while(T--) solve();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
/*
g++ game.cpp -o game -std=c++14 -O2 -DALEX_WEI
*/