题解：P9287 [ROI 2018] Viruses

DFbd · 2025-10-18 16:07:53 · 题解

显然，只有细胞 i 的易感染度最高的病毒编号是 i，病毒 i 才是稳定的。

接下来我们需要判断病毒是否可行。

只要有一个细胞可以使该病毒寄生并不会被消灭，该病毒就可行。

所以我们只需要枚举细胞，再枚举病毒寄生于该细胞是否可行。

而可行的条件即为，所有该细胞中易感染度高于该病毒的易感染度的病毒存活在初始细胞中，可以被易感染度低于该病毒的病毒直接消灭。

所以，我们将可以直接消灭存活于细胞 i 的病毒 i 的所有病毒向 i 连边，然后枚举细胞和病毒。

枚举病毒时，按照易感染度从低往高枚举，先判断是否可行，再将该点和与该点直接相邻的点打上标记，并统计标记个数。

若标记个数减去当前病毒的标记 \ge n - 1，该病毒可行。

#include <bits/stdc++.h>

using namespace std;

int n, a[505][505], p, cnt, f[505];
vector<int> ans, e[505];

void fill(int x) {
  f[x] = 1;
  cnt++;
  for (int i : e[x])
    if (!f[i]) {
      f[i] = 1;
      cnt++;
    }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int flag = 0;
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      if (a[i][j] == i)
        flag = 1;
      if (!flag)
        e[a[i][j]].push_back(i);
    }
    if (a[i][1] == i) {
      cnt++;
      ans.push_back(i);
    }
  }
  cin >> p;
  if (p == 1) {
    cout << cnt << '\n';
    for (int i : ans) 
      cout << i << ' ';
  } else {
    set<int> s;
    for (int i = 1; i <= n; i++) {
      cnt = 0;
      memset(f, 0, sizeof(f));
      for (int j = n; j; j--) {
        if (cnt - f[a[i][j]] >= n - 1)
          s.insert(a[i][j]);
        if (!f[a[i][j]]) 
          fill(a[i][j]); \\打标记
      }
    }
    cout << s.size() << '\n';
    for (int i : s)
      cout << i << ' ';
  }
  return 0;
}