zoj3811 Untrusted Patrol （dfs）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了zoj3811 Untrusted Patrol （dfs），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5571字，纯文字阅读大概需要8分钟。
内容图文
2014牡丹江网络赛C题 （第三水的题
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3811
|
Edward is a rich man. He owns a large factory for health drink production. As a matter of course, there is a large warehouse in the factory. To ensure the safety of drinks, Edward hired a security man to patrol the warehouse. The warehouse has N piles of drinks and M passageways connected them (warehouse is not big enough). When the evening comes, the security man will start to patrol the warehouse following a path to check all piles of drinks. Unfortunately, Edward is a suspicious man, so he sets sensors on K piles of the drinks. When the security man comes to check the drinks, the sensor will record a message. Because of the memory limit, the sensors can only record for the first time of the security man‘s visit. After a peaceful evening, Edward gathered all messages ordered by recording time. He wants to know whether is possible that the security man has checked all piles of drinks. Can you help him? The security man may start to patrol at any piles of drinks. It is guaranteed that the sensors work properly. However, Edward thinks the security man may not works as expected. For example, he may digs through walls, climb over piles, use some black magic to teleport to anywhere and so on. InputThere are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case: The first line contains three integers N (1 <= N <= 100000), M (1 <= M <= 200000) and K (1 <= K <= N). The next line contains K distinct integers indicating the indexes of piles (1-based) that have sensors installed. The following M lines, each line contains two integers Ai and Bi (1 <= Ai, Bi <= N) which indicates a bidirectional passageway connects piles Ai and Bi. Then, there is an integer L (1 <= L <= K) indicating the number of messages gathered from all sensors. The next line contains L distinct integers. These are the indexes of piles where the messages came from (each is among the K integers above), ordered by recording time. OutputFor each test case, output "Yes" if the security man worked normally and has checked all piles of drinks, or "No" if not. Sample Input2 5 5 3 1 2 4 1 2 2 3 3 1 1 4 4 5 3 4 2 1 5 5 3 1 2 4 1 2 2 3 3 1 1 4 4 5 3 4 1 2 Sample OutputNo Yes Author: DAI, Longao Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round |
题意：
给出一个无向图，一些点上有监视器，监视器能在维修工第一次到达该点时记录，给出所有监视器记录的顺序，判断维修工是否有可能在图中走完所有点。
输入：T组数据，每组第一行n，m，k，表示有n个点m条双向边，k个点有监视器。下一行有k个点表示装监视器的点的编号。然后m行是m条边。然后一个L是有记录的监视器的数量，下面一行是L个点，表明这些监视器按这个顺序记录了。
题解：DFS。
先判L不等于K的话，它就有点没走到，直接判no。
然后开个数组b[]，b[x]记录x点是由第几个监视器走到的。初始全部标为0，各个有监视器的点按最后一行输入的顺序标上1,2,3...L。
考虑监视器记录的情况，维修工需要在不经过3~L的情况下从1走到2，然后在不经过4~L的情况下从2走到3，依此类推。因为只记录第一次，走过的点是可以随便走的，所以从2走到3也就是从1或者2能到达的点走到3。这样，我们就每次从一个点dfs找看在不经过更高编号的点的情况下有没有路走到之前低编号的点走到的点。
从1~L号监视器的点依次开始dfs，不能经过b[x]比起始点高的点，只走b[x]=0的点，把走过的点标为b[x]=起点的b[]。并记录这次dfs是否能走到b[]比起始点小的点，不能的话就输出no。一直1~L都不no的话就输出yes。
具体是这样：我们有一个超碉变量now，表明这次dfs的起点。我们先从监视器1开始dfs，now=1，不能经过b[x]>1的点，并且把走过顶点都标为b[x]=1。
然后再从2开始，now=2，如果有边连向b[]<2的点，说明能走到比它小的监视器，把flag标为1。同样，这个dfs不能经过b[x]>2的点。
就这样对1~L号监视器都进行dfs。途中如果有一次dfs完flag为0，说明这个监视器和之前的监视器之间没有能走的路，就no。
代码不长，应该能直接看懂
代码：
1
//
#pragma comment(linker, "/STACK:102400000,102400000")
2 #include<cstdio>
3 #include<cmath>
4 #include<iostream>
5 #include<cstring>
6 #include<algorithm>
7 #include<cmath>
8 #include<map>
9 #include<set>
10 #include<stack>
11 #include<queue>
12usingnamespace std;
13#define ll long long
14#define usll unsigned ll
15#define mz(array) memset(array, 0, sizeof(array))
16#define minf(array) memset(array, 0x3f, sizeof(array))
17#define REP(i,n) for(i=0;i<(n);i++)
18#define FOR(i,x,n) for(i=(x);i<=(n);i++)
19#define RD(x) scanf("%d",&x)
20#define RD2(x,y) scanf("%d%d",&x,&y)
21#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
22#define WN(x) printf("%d\n",x);
23#define RE freopen("D.in","r",stdin)
24#define WE freopen("1biao.out","w",stdout)
25#define mp make_pair
26#define pb push_back
27constdouble eps=1e-10;
28constdouble pi=acos(-1.0);
29 30constint maxn=111111;
31constint maxm=444444;
32 33struct Edge {
34int v,next;
35} e[maxm];
36int head[maxn],en;
37 38void add(int x,int y) {
39 e[en].v=y;
40 e[en].next=head[x];
41 head[x]=en++;
42}
43 44int n,m,k,l;
45int a[maxn];
46 47int b[maxn];
48int now;
49bool flag;
50 51void dfs(int x) {
52//printf("[%d %d]\n",now,x); 53 b[x]=now;
54for(int i=head[x]; i!=-1; i=e[i].next) {
55int v=e[i].v;
56if(b[v]) {
57if (b[v]<now) {
58//printf("->%d b[%d]=%d\n",v,v,b[v]); 59 flag=1;
60 }
61continue;
62 }
63 dfs(v);
64 }
65return;
66}
67 68bool farm() {
69if(l<k)returnfalse;
70int i;
71 mz(b);
72 FOR(i,1,l) b[a[i]]=i;
73 now=1;
74 dfs(a[1]);
75 FOR(i,2,l) {
76 flag=0;
77 now=i;
78 dfs(a[i]);
79if(!flag)returnfalse;
80 }
81 FOR(i,1,n)if(!b[i])returnfalse;
82returntrue;
83}
84 85int main() {
86int T,x,y,i;
87 scanf("%d",&T);
88while(T--) {
89 scanf("%d%d%d",&n,&m,&k);
90 REP(i,k) {
91 scanf("%d",&x);
92 }
93 en=0;
94 memset(head,-1,sizeof(head));
95 REP(i,m) {
96 scanf("%d%d",&x,&y);
97 add(x,y);
98 add(y,x);
99 }
100 scanf("%d",&l);
101 FOR(i,1,l)scanf("%d",&a[i]);
102if(farm()) puts("Yes");
103else puts("No");
104 }
105return0;
106 }
原文：http://www.cnblogs.com/yuiffy/p/3961145.html
内容总结
以上是互联网集市为您收集整理的zoj3811 Untrusted Patrol （dfs）全部内容，希望文章能够帮你解决zoj3811 Untrusted Patrol （dfs）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。