UESTC 1811 Hero Saving Princess
题意:T个测试数据n m //n个点 m条边
m条无向边
que//下面有que个数据
a b // 表示a点的钥匙在b中
问,从0点开始能否遍历所有的点
思路:用BFS搜一遍即可,注意图是否连通,用并查集判断一下
BFS()时,q为正常队列,p为走到那个点是锁住时将q中点移到p中
#include <iostream> #include <string> #include <algorithm> #include <cstdio> #include <queue> #include <stdlib.h> #include <cstdlib> #include <math.h> #include <cstring> #include <set> #include <vector> #define inf 1073741824 #define N 100100 #define ll int using namespace std; inline ll Max(ll a,ll b){return a>b?a:b;} int lock[N],key[N],n,m;//lock=0表示没锁 ,key[i] 表示i房间中的钥匙,没有钥匙=-1 vector<int>G[N]; queue<int>q,p;//q表示bfs的没锁的点,p表示被锁的点 int f[N]; int find(int x){ if(f[x]==x)return x; return f[x]=find(f[x]); } bool vis[N],inp[N]; void BFS(){ memset(vis,0,sizeof(vis)); memset(inp,0,sizeof(inp)); q.push(0); vis[0]=true; int i,v,u,len; bool change=true; while(1) { change=false;//跳出条件是有新的点可以走 while(!q.empty()) { u=q.front(); q.pop(); len=G[u].size(); for(i=0;i<len;i++) { v=G[u][i]; if(lock[v]==-1) { if(inp[v]==false) p.push(v),inp[v]=true;//如果锁着且不在p中 continue; } if(vis[v]==false) { vis[v]=true; q.push(v); change=true; if(key[v]!=-1)//说明有钥匙 lock[key[v]]=0; } } } if(change==false)break; if(!p.empty()) { len=p.size(); while(len--) { int u=p.front();p.pop(); if(lock[u]>=0) //u点没有锁 q.push(u),vis[u]=true; else p.push(u); } } } } int main(){ int i,j,a,b,que; int T,Cas=1;scanf("%d",&T); while(T--){ memset(lock,0,sizeof(lock)); memset(key,-1,sizeof(key)); scanf("%d%d",&n,&m); for(i=0;i<n;i++)G[i].clear(),f[i]=i; while(m--) { scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); f[find(a)]=find(b); } scanf("%d",&que); while(que--) { scanf("%d%d",&b,&a); key[a]=b; lock[b]=-1; } for(i=0;i<n;i++)find(i); bool fu=false; for(i=0;i<n;i++) if(f[i]!=f[0]) { fu=true; break; } if(fu){printf("Case #%d: No\n",Cas++);continue;} while(!q.empty())q.pop(); while(!p.empty())p.pop(); if(key[0]!=-1)lock[key[0]]=0;//起点房间如果有钥匙直接开门 BFS(); if(!p.empty())printf("Case #%d: No\n",Cas++);//p表示锁着的门,如果还有锁着的门就说明没有走到所有的点 else printf("Case #%d: Yes\n",Cas++); } return 0; } /* 99 2 1 0 1 0 3 2 0 1 1 2 1 1 2 7 9 0 1 2 0 2 5 5 1 5 6 5 2 1 3 3 6 1 4 3 4 2 2 0 6 4 7 9 0 1 2 0 2 5 5 1 5 6 5 2 1 3 3 6 1 4 1 2 2 3 4 0 1 1 0 0 1 2 0 2 1 2 2 1 1 0 0 2 1 1 0 1 1 1 2 1 1 0 1 1 0 2 0 0 ans: y n y n n y n y */
补充:软件开发 , C++ ,