首页 > > 程序设计 > C/C++ >

P2712 摄像头

2018-06-17 22:39:19来源：未知阅读 ()

题目描述

食品店里有n个摄像头，这种摄像头很笨拙，只能拍摄到固定位置。现有一群胆大妄为的松鼠想要抢劫食品店，为了不让摄像头拍下他们犯罪的证据，他们抢劫前的第一件事就是砸毁这些摄像头。

为了便于砸毁摄像头，松鼠歹徒们把所有摄像头和摄像头能监视到的地方统一编号，一个摄像头能被砸毁的条件是该摄像头所在位置不被其他摄像头监视。

现在你的任务是帮松鼠们计算是否可以砸掉所有摄像头，如不能则输出还没砸掉的摄像头的数量。

输入输出格式

输入格式：

第1行，一个整数n，表示摄像头的个数。

第2到n+1行是摄像头的信息，包括：摄像头的位置x，以及这个摄像头可以监视到的位置数m，之后m个数y是此摄像头可以监视到的位置。(砸了这些摄像头之后自然这些位置就监视不到了)

输出格式：

若可以砸掉所有摄像头则输出“YES”，否则输出还没砸掉的摄像头的数量。

输入输出样例

输入样例#1：

输出样例#1：

神坑题啊，，，，

一没数据数据范围，二题目描述不清楚

“第2到n+1行是摄像头的信息，包括：摄像头的位置x”

这句话的意思就是和你说

一开始遍历的时候只需要遍历到n

查找答案的时候需要查找摄像头的位置

还有就是map其实可以省去。。。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<map>
 7 using namespace std;
 8 map<int,int>mp;
 9 const int MAXN=1000001;
10 struct node
11 {
12     int u;
13     int v;
14     int next;
15 }edge[MAXN];
16 int head[MAXN];
17 int num=1;
18 int rudu[MAXN];
19 int n;
20 void add(int where,int will)
21 {
22     edge[num].u=where;
23     edge[num].v=will;
24     edge[num].next=head[where];
25     head[where]=num++;
26 }
27 void topsort()
28 {
29     queue<int>q;
30     for(int i=1;i<=n;i++)
31         if(rudu[i]==0)
32             q.push(i);
33     while(q.size()!=0)
34     {
35         int p=q.front();
36         q.pop();
37         for(int i=head[p];i!=-1;i=edge[i].next)
38         {
39             if(edge[i].u==0&&edge[i].v==0)break;
40             int to=edge[i].v;
41             rudu[to]--;
42             if(rudu[to]==0)
43                 q.push(to);
44         }
45     }
46         int ans=0;
47         for(int i=1;i<=n;i++)
48             if(rudu[mp[i]]!=0)
49                 ans++;
50         if(ans==0)
51         printf("YES");
52         else
53         printf("%d",ans);
54 }
55 int main()
56 {
57     scanf("%d",&n);
58     for(int i=1;i<=n;i++)head[i]=-1;
59     for(int i=1;i<=n;i++)
60     {
61         int where,m,will;
62         scanf("%d%d",&where,&m);
63         mp[i]=where;
64         for(int j=1;j<=m;j++)
65         {
66             scanf("%d",&will);
67             rudu[will]++;
68             add(mp[i],will);
69         }
70     }
71     topsort();
72     return 0;
73 }