自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:46:00，当前版本为作者最后更新于2023-04-12 20:38:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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 一定会让这条边产生贡献。

对于环上的边：

• 环大小为 $1$，则只要 Alice 可以选就一定产生贡献。
• 环大小大于 $1$，则有两种定向方案。Bob 一定选代价较小的那个，Alice 的目标是让代价较小的方案的代价最大化。设 $c_u, c_v, c$ 分别表示只能选 $u$，只能选 $v$，两个都可以选的边数，相当于求 $\max_{i = 0} ^ c \min(c_u + i, c_v + c - i)$。不妨设 $c_u < c_v$，则当 $c_u + c < c_v$ 时，贡献为 $c_u + c$，否则贡献为 $\lfloor\frac {c_u + c_v + c} 2\rfloor$。

对于 $\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
*/