题解：P9287 [ROI 2018] Viruses

注意到，这是一道假扮成 OI 题的语文阅读理解题。

## 题意

有 $n$ 个细胞和 $n$ 种病毒，编号均 $1 \sim n$。

每个时刻每个细胞都会感染恰好一个病毒。令当前细胞 $i$ 中感染的病毒编号为 $c_i$。最开始第 $i$ 个细胞感染的病毒是 $i$，即 $c_i = i$。

在每个细胞心目中都有对每个病毒的能力的排名。即给定一个 $n \times n$ 的矩阵 $a$，其中 $a_{i, j}$ 表示在第 $i$ 个细胞心目中，病毒 $j$ 是**第几强**的。例如若 $a_{1,1}=2,a_{1,2}=1,a_{1,3}=3$ 则表示细胞 $1$ 认为病毒 $2$ 最强，病毒 $1$ 其次，病毒 $3$ 最菜。

细胞会互相攻击。当细胞 $i$ 攻击细胞 $j$ 时，如果 $a_{j,c_i} > a_{j,c_j}$，则细胞 $j$ 将会感染病毒 $c_i$，即 $c_j \gets c_i$。即当细胞 $j$ 认为 $i$ 的病毒更强时，它会放弃自己现有的病毒，而感染更强的。

细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。显然游戏的最终局面（$c_1\dots c_n$）可能不唯一。

我们定义在某个游戏的最终局面里，一个病毒是「牛的」，**这个病毒没有灭绝**，即存在至少一个细胞感染了这个病毒。

你需要解决两个问题：

- 求哪些病毒是「稳定的」。一个病毒是稳定的，当且仅当这个病毒在**所有**游戏的最终局面里都是牛的。
- 求哪些病毒是「可行的」。一个病毒是稳定的，当且仅当这个病毒在**至少一种**游戏的最终局面里是牛的。

## Part.1 「稳定的病毒」

考虑求解哪些病毒是「稳定的」。

我们断言病毒 $i$ 是「稳定的」当且仅当 $a_{i, 1} = i$，即细胞 $i$ 认为病毒 $i$ 是最强的。

我们考虑题目中描述的能够发生感染的条件：

> 当细胞 $i$ 攻击细胞 $j$ 时，……，当细胞 $j$ 认为 $i$ 的病毒更强时，它会放弃自己现有的病毒，而感染更强的。

我们知道细胞 $i$ 最开始感染的是病毒 $i$，所以细胞 $i$ 最开始感染的就是它认为的最强的病毒。而接下来的感染过程如果能够发生，就代表感染源是一种（细胞 $i$ 认为的）更强的病毒。显然这矛盾。

## Part.2 「可行的病毒」

考虑求解哪些病毒是「可行的」。

首先以 $\mathcal O(n)$ 的复杂度枚举 $i$，表示我们要**判断病毒 $i$ 是否「可行」**。

根据题目描述，如果病毒 $i$ 可行，那么当游戏结束时它一定存在于某个细胞内。不妨再以 $\mathcal O(n)$ 的复杂度枚举 $j$ 表示判断是否存在一种游戏的最终局面，使得**细胞 $j$ 感染了病毒 $i$**。如果不存在这样的 $j$ 则病毒 $i$ 不是「可行的」。

游戏结束的条件是不存在任何一对细胞可以攻击。那么如果病毒 $k$ 满足它在细胞 $i$ 心中比病毒 $j$ 要强（即 $a_{i, k} < a_{i, j}$），而且存在一个细胞 $l$（$l \ne i$） 感染了病毒 $k$，那么当前游戏是不能结束的。因为细胞 $l$ 还可以攻击细胞 $j$。

这给我们的启发是，只有在当前局面里，细胞 $i$ 心目中比病毒 $j$ 强的病毒都**灭绝**（即不存在任何一个细胞感染这个病毒）时，游戏才会在此时结束。而此时结束就满足了我们的设想：细胞 $j$ 感染了病毒 $i$。

所以我们现在要判断是否每个（在细菌 $j$ 心目中）比病毒 $i$ 强的病毒 $k$ 都存在至少一种方案灭绝。

如何把病毒 $k$ 灭绝？我们知道（在细菌 $j$ 心目中）比病毒 $i$ 弱的病毒存在是没有影响的，所以我们可以用这些病毒把病毒 $k$ 灭绝。

把病毒 $k$ 灭绝还需要满足一个条件，就是杀它的病毒（在细菌 $k$ 心目中）要比病毒 $k$ 强。因此我们把满足上个条件的病毒标记，然后枚举（在细菌 $k$ 心目中）比病毒 $k$ 强即可。

## 代码

```cpp
int n, p, a[N][N], b[N][N];
// a[i][j] 表示在细菌 i 心目中第 j 强的病毒
// b[i][j] 表示在细菌 i 心目中第 j 个病毒的排名
bool st[N];		// 把在细菌 j 心目中比病毒 i 强的病毒标记

signed main() {
	cin >> n;
	
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= n; ++ j ) {
			cin >> a[i][j];
			b[i][a[i][j]] = j;
		}
	
	vector<int> res;
	cin >> p;
	if (p == 1) {
		for (int i = 1; i <= n; ++ i )
			if (a[i][1] == i) res.push_back(i);
	} else {
		for (int i = 1; i <= n; ++ i ) {		// 判断病毒 i 能否活下来
			bool Alive = false;			// 判断病毒 i 能否在任意一个细菌 j 中活下来
			for (int j = 1; j <= n && !Alive; ++ j )
				if (b[j][i] <= b[j][j]) {				// 首先它要比细菌 j 中最初的病毒（病毒 j）要强，不然没机会
					memset(st, 0, sizeof st);
					
					for (int k = 1; k < b[j][i]; ++ k ) {
						st[a[j][k]] = true;		// 把在细菌 j 心目中比病毒 i 强的病毒标记
					}
					
					bool all_destroyed = true;		// 判断在细菌 j 心目中比病毒 i 强的病毒标记是否都灭绝
					for (int k = 1; k < b[j][i] && all_destroyed; ++ k ) {
						int x = a[j][k];		// 取出一个在细菌 j 心目中比病毒 i 强的病毒
						
						bool ok = false;		// 判断是否存在一个没有标记的病毒，且在细菌 x 心目中比病毒 x 强
						for (int l = 1; l < b[x][x] && !ok; ++ l )
							if (!st[a[x][l]]) ok = true;
						
						if (!ok) all_destroyed = false;
					}
					
					if (all_destroyed) Alive = true;
				}
			
			if (Alive) res.push_back(i);
		}
	}
	
	cout << res.size() << '\n';
	for (int v : res) cout << v << ' ';
	
	return 0;
}
```

正在渲染内容...