昨天網(wǎng)賽的C題，我負(fù)責(zé)的，題意有些模模糊糊的

我首先弄清楚了題意，即要求一個(gè)patrol是否可能巡視過(guò)所有的點(diǎn)，首先整個(gè)圖要是連通的，這個(gè)在建圖的時(shí)候邊用下并查集即可，然后某些點(diǎn)裝了傳感器，傳感器應(yīng)該要全部都響應(yīng)過(guò)才行，即L==k否則直接輸出No，然后就是重點(diǎn)，給出的傳感器的響應(yīng)先后順序，我們要在圖上找到這樣一種路徑，路徑上的傳感器的先后順序正好對(duì)應(yīng)了給出的記錄，找不到則是No，找到了就是Yes。

我一開(kāi)始看到點(diǎn)有10萬(wàn)個(gè)，想用DFS+回溯嘗試每種路徑，最多20W條的路，但是路徑種樹(shù)就遠(yuǎn)遠(yuǎn)不止了。。所以抱著嘗試的心態(tài)，這樣的子TLE了就知道不是這種方法了。

后來(lái)就是我坑了，聰哥想了一種BFS的方法，只要對(duì)所有點(diǎn)遍歷一遍即可，我聽(tīng)了兩遍才搞清楚，而且還歪曲了其中一個(gè)重要的思想，導(dǎo)致第一次敲出的BFS還WA了一發(fā)。他給我講完之后，我理解的思路是從傳感器的第一個(gè)出發(fā)，往下進(jìn)行搜索，是普通點(diǎn)就vis掉加入隊(duì)列，是我們當(dāng)前要找的下一個(gè)傳感器就也vis掉加入隊(duì)列，并且把一個(gè)cur標(biāo)記++，這樣如果存在這樣的路徑，最后的cur就==k，然后這種方法其實(shí)是錯(cuò)的，這就是我忽略了聰哥給我講的思想的重要一點(diǎn)，因?yàn)轭}目里面?zhèn)鞲衅魇侵挥涗浀谝淮蔚竭_(dá)的時(shí)間，所以可以來(lái)回走，這么說(shuō)的話(huà)，我要找的傳感器的序列 不一定要是真的存在一條路徑上，只要走回之前的點(diǎn)，能找到下一個(gè)新的傳感器也是合理的

。。。

所以這就不能用普通的找路徑的BFS了，我用個(gè)染色標(biāo)記，記錄當(dāng)前傳感器是否已經(jīng)被訪(fǎng)問(wèn)過(guò)，首先把第一個(gè)傳感器標(biāo)記，并且打入隊(duì)列，然后走一遍BFS，把所有可以訪(fǎng)問(wèn)到的傳感器都染色一下，但不入隊(duì)列，之后又對(duì)下一個(gè)傳感器首先判斷是否被染過(guò)色，染過(guò)就入隊(duì)列，像剛剛一樣，BFS，把之后可能遍歷到的傳感器又染色。。如果我下一個(gè)要進(jìn)隊(duì)列的傳感器沒(méi)有被染過(guò)色，直接return false，因?yàn)檎f(shuō)明肯定沒(méi)有這樣的路徑能直接進(jìn)入下一個(gè)傳感器。。。如果整個(gè)能一套走完就返回true

這樣子BFS首先保證了傳感器的訪(fǎng)問(wèn)順序嚴(yán)格按要求，中間不會(huì)插入其他傳感器，并且因?yàn)槲颐看伟旬?dāng)前傳感器 ，對(duì)之后可能遍歷到的傳感器都染色，這樣對(duì)于來(lái)回走的情況也考慮到了，不會(huì)漏情況

之前聰哥給我講的時(shí)候，沒(méi)領(lǐng)會(huì)這個(gè)重要思想，弄得搞半天才出來(lái)。這個(gè)怪我。而且這個(gè)其實(shí)應(yīng)該容易想到，至少我上面那種錯(cuò)誤的BFS方法要可以想的到，居然在那里呆了好久，都沒(méi)想到。

#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 ; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/kkrisen/p/3961481.html

總結(jié)

以上是生活随笔為你收集整理的zoj 3811 untrusted patrol的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。