P2712的一点小理解 - 洛谷保存站

[题目传送门](https://www.luogu.com.cn/problem/P2712)

## Part.0. 闲话

没错，又是我 [^1]。在上次的 [P5076的一点小理解](https://www.luogu.com.cn/article/266l6yoh) 中说我真的是个 $\color{cyan}{蒟蒻}$ ，事实上也确实如此，在9.16的考试中也是轻松 $AK$ 了20分啊，荣获倒数第三。

我当时最认为可以100tps的题目就是这道摄像头啊，而且只花了40min（别喷，这对我来说已经很快了）就过了样例，当时我也没管，就放在那打其它题目了（后来被所有题题吊着打），结果当我提交答案时它惊人地告诉我：[ $\color{red}{10分！}$ ](https://www.luogu.com.cn/record/177168800)

我考完后心态就崩了啊，就连饭都不吃就在这里改代码，终于是在13:05时没看题解凭借自己的力量打出来了。

注：本篇文章有些地方和已审核题解有相似之处（毕竟都是拓扑排序），勿喷

## Part.1. 思路

这道题很明显就是 `topo sort` 嘛，所谓「没有被监视的摄像头」，就是在寻找入度为0的结点，再ban掉它的子节点，然后重复操作直至不能进行，这时再判断还有几个点没有被删除就可以了。

题意不难理解， _但是！！_ 题目中只说标了序号，却没说按顺序标号啊！[^2]

因此，我们需要用一个 `w[]` 数组来存一下这些点的位置。

剩下的，就是 `dfs` ~~大法师~~ 和寻找 `ans` 的过程了，不赘述。

>好的思路是成功的一半。
>—— ~闲子~ 氙子Xenon

那么，开工大吉！

## Part.2. 主体

反正大家都是诚实守信的五星好市民，而且这道题没 [P5076](https://www.luogu.com.cn/problem/P5076) 好分步解析，思路对了题目就没什么难度了，直接端上代码！

```cpp
#include "bits/stdc++.h"
using namespace std;
struct node{
	int w;
	int to[2200];
	int tonum;
	int din;
} cam[2200];
int n, m, x, to, ans, w[2200];
void dfs(){
	for (int i = 1; i <= n; i++){
		if (cam[w[i]].din == 0 && cam[w[i]].w != 0){
			cam[w[i]].w = 0;
			for (int j = 0; j < cam[w[i]].tonum; j++) cam[cam[w[i]].to[j]].din--;
			dfs();
		}
	}
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> x >> m;
		cam[x].tonum = m;
		cam[x].w = x;
		w[i] = x;
		for (int j = 0; j < m; j++){	
			cin >> to;
			cam[x].to[j] = to;
			cam[cam[x].to[j]].din++;
		}
	}
	dfs();
	for (int i = 1; i <= n; i++)
		if (cam[w[i]].w != 0) ans++;
		
	if (ans != 0) cout << ans;
	else cout << "YES";
	return 0;
}
/*
输入：
6
98 1 151
100 2 98 120
120 0
151 1 160
160 2 98 100
500 1 120
输出：
5
*/
//附赠比样例好得多的数据 诶嘿

```

不加注释（除了最后面的手搓数据）的原因是，我觉得我的代码可读性还算高，真的不是因为懒，毕竟前面都说了思路嘛。

## Part.3. 总结

这道题应该算是一道实至名归的 $\color{F0DE1B}{黄题}$ ，基本上算一道板子题吧。但是也有些坑点，例如题面在背后偷偷搞你一下，而且官方样例未免也太水了（我10tps的代码都过得了样例，也是有点离谱的，所以一定要自己搓一个难点的样例啊！），因此确实是黄题，但应该也只能算黄题了。

## Part.4. 尾声

终于写完了！这道阴了我的题。虽然这道题也是被我吃透了，但是考成那个集贸样，也不知道会不会被教练骂。

哎，听天由命吧！

[![](https://jrenc.azurewebsites.net/api/signature?code=zHZRCCItO-yB8t7d2KyitELFDwADnXIotkeeIQL3juyNAzFucnyrWA%3D%3D&name=thanks%20for%20reading%20%20%20%20%20%20%20%20by%20%40Xianzi_(591561)&animate=true&speed=2&color=darkcyan)](www.luogu.com/user/591561)

---

[^1]: 这是我的第二篇题解了（为什么我每次在遭遇考试打击后就能写出题解了？我不理解）

[^2]: 原文：「摄像头的位置 $x$」「有 $n$ 个摄像头」

正在渲染内容...