P2712的一点小理解

· · 题解

题目传送门

Part.0. 闲话

没错，又是我 ^1。在上次的 P5076的一点小理解 中说我真的是个 \color{cyan}{蒟蒻} ，事实上也确实如此，在9.16的考试中也是轻松 AK 了20分啊，荣获倒数第三。

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

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

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

Part.1. 思路

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

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

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

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

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

那么，开工大吉！

Part.2. 主体

反正大家都是诚实守信的五星好市民，而且这道题没 P5076 好分步解析，思路对了题目就没什么难度了，直接端上代码！

#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. 尾声

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

哎，听天由命吧！

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