题解：P9697 [GDCPC 2023] Canvas

· · 题解

我们发现 x 和 y 只能为 1 或 2 也就是说，总共只有 3 种情况。

对于 (1, 1) 肯定是最早选，这样好被后面的大数覆盖。

对于 (2, 2) 肯定是最晚选，这样才不会被覆盖。

对于 (1, 2) 我们需要采用尽可能用下一个的 2 覆盖这个的 1 的策略。

具体该如何实施呢？我们发现覆盖操作难以实施，正难则反，我们采用从后往前覆盖，这样只需使已经操作过的序列元素不可被再次操作即可。

在最优策略下，一定是前一个 (1, 2) 的 2 盖住下一个 (1, 2) 的 1，如此不断连锁。于是我们把前一个 (1, 2) 视为一个点，并向能盖住 1 的所有 (1, 2) 连一条有向边。于是就形成了一张图。

对于这张图上入度为 0 的点，由于它要盖住别的点且没点盖它，所以得先插入。

可能会出现没有入度 0 的点，所以要先缩点，然后跑拓扑排序，注意一个强连通分量里的点，并不能按照 tarjan 的出栈顺序依次覆盖，而是要从之前已经覆盖的位置开始，以 dfs 序进行操作。

然后就结束了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10, K = 20, mod = 1e9 + 7;
int n, m, dfn[N], ar, low[N], ins[N], scc[N], col, cnti[N], rl[N], vis[N];
vector <int> edge[N], blg[N], rol[N], sedge[N];
stack <int> st;
stack <int> out;
int chkmn(int &a, const int &b) {return a = min(a, b);}
void tarjan(int p)
{
  dfn[p] = low[p] = ++ ar;
  st.push(p); ins[p] = 1;
  for (auto to : edge[p])
  {
    if (!dfn[to])
    {
      tarjan(to);
      chkmn(low[p], low[to]);
    }
    else if (ins[to])
      chkmn(low[p], dfn[to]);
  }
  if (low[p] == dfn[p])
  {
    col ++;
    while (!st.empty())
    {
      int t = st.top(); st.pop();
      ins[t] = 0;
      scc[t] = col;
      blg[col].emplace_back(t);
      if (t == p)
        break;
    }
    reverse(blg[col].begin(), blg[col].end());
  }
}
vector <pair<int, int>> rest, mid;
vector <int> mp, mp2;
void dfs(int p)
{
  vis[p] = 1;
  if (rl[mid[p].first] == 0)
    rl[mid[p].first] = 1;
  if (rl[mid[p].second] == 0)
    rl[mid[p].second] = 2;
  out.push(mp2[p]);
  for (auto to : edge[p]) if (!vis[to] && scc[to] == scc[p])
  {
    dfs(to);
  }
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int _;
  cin >> _;
  while (_ --){
    cin >> m >> n;
    rest = vector <pair<int, int>>(), mid = vector <pair<int, int>>(1);
    mp = vector <int>(n + 1), mp2 = vector <int>(n + 1);
    for (int i = 1; i <= n; i ++)
    {
      int l, x, r, y;
      cin >> l >> x >> r >> y;
      if (x > y) swap(x, y), swap(l, r);
      if (x == 2)
        rl[l] = rl[r] = 2, out.push(i);
      else if (y == 1)
        rest.emplace_back(l, r), mp[rest.size() - 1] = i;
      else
        mid.emplace_back(l, r), rol[l].emplace_back(mid.size() - 1), mp2[mid.size() - 1] = i;
    }
    for (int i = 1; i < mid.size(); i ++)
      for (auto it : rol[mid[i].second]) edge[i].emplace_back(it);
    for (int i = 1; i < mid.size(); i ++) if (!dfn[i]) tarjan(i);
    for (int i = 1; i < mid.size(); i ++)
      for (auto to : edge[i])
        if (scc[to] != scc[i]) cnti[scc[to]] ++, sedge[scc[i]].emplace_back(scc[to]);
    queue <int> q;
    for (int i = 1; i <= col; i ++)
      if (cnti[i] == 0)
      {
        q.push(i);
      }
    while (!q.empty())
    {
      int f = q.front(); q.pop();
      int st = 0;
      for (int i = 0; i < blg[f].size(); i ++)
        if (rl[mid[blg[f][i]].first])
        {
          st = i;
          break;
        }
      dfs(blg[f][st]);
      for (auto to : sedge[f])
      {
        if (--cnti[to] == 0)
        {
          q.push(to);
        }
      }
    }
    for (int i = 0; i < rest.size(); i ++)
    {auto [u, v] = rest[i]; rl[u] = max(rl[u], 1ll), rl[v] = max(rl[v], 1ll), out.push(mp[i]);}
    int ans = 0; for (int i = 1; i <= m; i ++) ans += rl[i];//, cout << rl[i] << " "; cout << endl;
    cout << ans << '\n';
    while (!out.empty())
    {
      cout << out.top() << " ";
      out.pop();
    }
    cout << '\n';
    while (!st.empty())
      st.pop();
    for (int i = 1; i <= n; i ++)
    {
      edge[i].clear(), blg[i].clear(), sedge[i].clear();
      dfn[i] = 0, low[i] = 0, scc[i] = 0, cnti[i] = 0, ins[i] = 0, vis[i] = 0;
    }
    ar = 0, col = 0;
    for (int i = 1; i <= m; i ++)
    {
      rol[i].clear();
      rl[i] = 0;
    }
  }
  return 0;
}