首页 > 代码库 > zoj 3811 untrusted patrol
zoj 3811 untrusted patrol
昨天网赛的C题，我负责的，题意有些模模糊糊的
我首先弄清楚了题意，即要求一个patrol是否可能巡视过所有的点，首先整个图要是连通的，这个在建图的时候边用下并查集即可，然后某些点装了传感器，传感器应该要全部都响应过才行，即L==k否则直接输出No，然后就是重点，给出的传感器的响应先后顺序，我们要在图上找到这样一种路径，路径上的传感器的先后顺序正好对应了给出的记录，找不到则是No，找到了就是Yes。
我一开始看到点有10万个，想用DFS+回溯尝试每种路径，最多20W条的路，但是路径种树就远远不止了。。所以抱着尝试的心态，这样的子TLE了就知道不是这种方法了。
后来就是我坑了，聪哥想了一种BFS的方法，只要对所有点遍历一遍即可，我听了两遍才搞清楚，而且还歪曲了其中一个重要的思想，导致第一次敲出的BFS还WA了一发。他给我讲完之后，我理解的思路是从传感器的第一个出发，往下进行搜索，是普通点就vis掉加入队列，是我们当前要找的下一个传感器就也vis掉加入队列，并且把一个cur标记++，这样如果存在这样的路径，最后的cur就==k，然后这种方法其实是错的，这就是我忽略了聪哥给我讲的思想的重要一点，因为题目里面传感器是只记录第一次到达的时间，所以可以来回走，这么说的话，我要找的传感器的序列 不一定要是真的存在一条路径上，只要走回之前的点，能找到下一个新的传感器也是合理的
。。。
所以这就不能用普通的找路径的BFS了，我用个染色标记，记录当前传感器是否已经被访问过，首先把第一个传感器标记，并且打入队列，然后走一遍BFS，把所有可以访问到的传感器都染色一下，但不入队列，之后又对下一个传感器首先判断是否被染过色，染过就入队列，像刚刚一样，BFS，把之后可能遍历到的传感器又染色。。如果我下一个要进队列的传感器没有被染过色，直接return false，因为说明肯定没有这样的路径能直接进入下一个传感器。。。如果整个能一套走完就返回true
这样子BFS首先保证了传感器的访问顺序严格按要求，中间不会插入其他传感器，并且因为我每次把当前传感器 ，对之后可能遍历到的传感器都染色，这样对于来回走的情况也考虑到了，不会漏情况
之前聪哥给我讲的时候，没领会这个重要思想，弄得搞半天才出来。这个怪我。而且这个其实应该容易想到，至少我上面那种错误的BFS方法要可以想的到，居然在那里呆了好久，都没想到。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int N = 100010;int n,m,k,L;int order[N];int inq[N];vector<int> G[N];int fa[N];int vis[N];int a,b;int findset(int x){ if (x!=fa[x]){ fa[x]=findset(fa[x]); } return fa[x];}bool bfs(){ queue<int> q; vis[order[0]]=1; for (int i=0;i<L;i++){ if (vis[order[i]]) q.push(order[i]); else return false; while (!q.empty()) { int u=q.front(); q.pop(); for (int i=0;i<G[u].size();i++){ int v=G[u][i]; if (inq[v]) vis[v]=1; else { if (vis[v]) continue; vis[v]=1; q.push(v); } } } } return true;}int main(){ int t; scanf("%d",&t); while (t--) { scanf("%d%d%d",&n,&m,&k); for (int i=0;i<=n;i++){ G[i].clear(); fa[i]=i; vis[i]=0; inq[i]=0; } for (int i=0;i<k;i++){ scanf("%d",&order[i]); inq[order[i]]=1; } while (m--) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); int r1=findset(a); int r2=findset(b); if (r1!=r2) fa[r1]=r2; } scanf("%d",&L); for (int i=0;i<L;i++) scanf("%d",&order[i]); if (L<k){ puts("No"); continue; } int rt=findset(n); bool flag=1; for (int i=1;i<n;i++){ if (findset(i)!=rt){ flag=0; break; } } if (!flag) { puts("No"); continue; } flag=bfs(); if (flag) puts("Yes"); else puts("No"); } return 0 ;}
zoj 3811 untrusted patrol