首页 > 代码库 > ZOJ-3811 Untrusted Patrol DFS 2014牡丹江网络赛C题
ZOJ-3811 Untrusted Patrol DFS 2014牡丹江网络赛C题
n个点,m条双向边,k个传感器。其中有l个传感器记录到了第一次到达的时间顺序,求是否有可能检查了所有的顶点。
首先判断l,l<k一定是不行的。然后按照传感器的时间顺序dfs,先从第一个传感器位置搜索dfs搜到所有的到达传感器的位置结束,如果这个传感器被标记为可访问,则从这个传感器继续搜索下一层传感器,否则是不能满足时间顺序的。最后还要判断整个图的连通性,所有的顶点都要可以到达的。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <cmath> #include <iomanip> #include <cstdlib> #include <algorithm> using namespace std; const int maxn=110000; int head[maxn]; int visit[maxn]; int pile[maxn]; int n,m,k,l; int num; int s; struct Edge { int u,v; int next; }edge[maxn*4]; void addedge(int u,int v) { edge[num].u=u; edge[num].v=v; edge[num].next=head[u]; head[u]=num++; edge[num].u=v; edge[num].v=u; edge[num].next=head[v]; head[v]=num++; } void dfs(int u) { visit[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(visit[v]) { continue; } if(pile[v]) { visit[v]=1; continue; } dfs(v); } } void dfs1(int u) { visit[u]=1; s++; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!visit[v]) { dfs1(v); } } } int main() { int t; int flag; int u,v; scanf("%d",&t); while(t--) { flag=1; s=0; num=0; memset(head,-1,sizeof(head)); memset(visit,0,sizeof(visit)); memset(pile,0,sizeof(pile)); scanf("%d%d%d",&n,&m,&k); for(int i=0;i<k;i++) { scanf("%d",&u); pile[u]=1; } for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); addedge(u,v); } scanf("%d",&l); if(l<k) { flag=0; } scanf("%d",&u); dfs(u); for(int i=1;i<l;i++) { scanf("%d",&u); if(!visit[u]) { flag=0; } if(flag) { dfs(u); } } memset(visit,0,sizeof(visit)); dfs1(1); if(s<n) { flag=0; } if(flag) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }
ZOJ-3811 Untrusted Patrol DFS 2014牡丹江网络赛C题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。