A.两个按钮

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF520B 题型：bfs广搜 题意：显示屏显示正整数n 红色按钮：数字×2 蓝色按钮：数字-1 限制：数字必须始终保持为正整数（≥1） 目标：从n变到m 求：最少按多少次 思路：这是一个最短路径问题，适合广搜找最短路径，每次x2或-1。

#include<bits/stdc++.h>
using namespace std;
int n,m,v[20005],q[20005],l=0,r=0,ans;
int main(){
	cin>>n>>m;
	v[n]=1;
	q[r++]=n;
	while(l<r){
		int x=q[l++];
		if(x==m){
			ans=v[x]-1;
			break;
		}
		if(x*2<=20000&&!v[x*2]){
			v[x*2]=v[x]+1;
			q[r++]=x*2;
		}
		if(x-1>=1&&!v[x-1]){
			v[x-1]=v[x]+1;
			q[r++]=x-1;
		}
	}
	cout<<ans;
	return 0;
}

B.着火了

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF35C 题型：广搜 题意：有一个n×m的网格，每棵树是一个格子。初始有K个格子已经着火。每分钟，如果一个格子的上下左右四个方向有相邻格子着火，那么它也会着火。问：最后一个着火的格子是哪个？ 输出任意一个即可。这实际上是一个多源BFS问题，求所有格子到最近火源的最大距离（最远距离）。 思路：从K个火源同时开始BFS，记录每个格子被点燃的时间。最后一个被点燃的格子就是时间最大的那个格子

#include<bits/stdc++.h>
using namespace std;
int a[2005][2005],n,m,k,q[4000005][2],l=0,r=0,s,dx[]={-1,1,0,0},dy[]={0,0,-1,1},ax,ay;
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		a[x][y]=1;
		q[r][0]=x;
		q[r][1]=y;
		r++;
	}
	s=k;
	while(l<r){
		int x=q[l][0];
		int y=q[l][1];
		l++;
		ax=x;
		ay=y;
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]==0){
				a[nx][ny]=1;
				q[r][0]=nx;
				q[r][1]=ny;
				r++;
				s++;
			}
		}
	}
	cout<<ax<<" "<<ay;
	return 0;
}

C.公园散步

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF1106D 题型：BFS 题意：小k从节点1出发，每到一个未记录过的节点就记录下来。当他访问完所有节点后停止。问：能得到的字典序最小的节点序列是什么？ 思路：从节点1开始，把节点1加入优先队列（最小堆），每次从堆中取出编号最小的节点，如果这个节点还没被访问过，就记录下来，把这个节点的所有邻居加入堆（如果没被访问过），重复直到访问完所有节点

#include<bits/stdc++.h>
using namespace std;
int v[100005],ans[100005];
vector<int>e[100005];
priority_queue<int,vector<int>,greater<int>>zx;
int main(){
	int n,m,u,s,cnt=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>s;
		if(u==s)continue;
		e[u].push_back(s);
		e[s].push_back(u);
	}
	v[1]=1;
	zx.push(1);
	while(!zx.empty()){
		int x=zx.top();
		zx.pop();
		ans[++cnt]=x;
		for(int i=0;i<e[x].size();i++){
			int y=e[x][i];
			if(!v[y]){
				v[y]=1;
				zx.push(y);
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	return 0;
}

D.修路

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF954D 题型：BFS 题意：给定一个无向连通图s和t是两个特殊节点。定义 d(s,t)为s到t的最短距离（边数）。现在要添加一条新边 (u,v)，其中u,v之间原本没有边。问：有多少对(u,v)满足，添加这条边后，d(s,t) 不会变小？ 思路：预处理：从s和t分别跑BFS，得到 distS[i]和distT[i]，原最短路：d=distS[t]，枚举所有未连接的 (u,v)：检查是否满足条件，统计答案

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,ds[1005],dt[1005],v[1005],q[1005],l=0,r=0,ans;
vector<int>e[1005];
void bfs(int x,int d[]){
	memset(v,0,sizeof(v));
	l=0;
	r=0;
	v[x]=1;
	d[x]=0;
	q[r++]=x;
	while(l<r){
		int u=q[l++];
		for(int i=0;i<e[u].size();i++){
			int w=e[u][i];
			if(!v[w]){
				v[w]=1;
				d[w]=d[u]+1;
				q[r++]=w;
			}
		}
	}
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	bfs(s,ds);
	bfs(t,dt);
	int c=ds[t];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int f=1;
			for(int k=0;k<e[i].size();k++){
				if(e[i][k]==j){
					f=0;
					break;
				}
			}
			if(!f)continue;
			int nd=min(ds[i]+1+dt[j],ds[j]+1+dt[i]);
			nd=min(nd,c);
			if(nd==c)ans++;
		}
	}
	cout<<ans;
	return 0;
}

E.火车或巴士

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF601A

E.火车或巴士

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF601A?lang=zh 题意：有一个n个点的完全图，每条边要么是铁路，要么是公路，两者互补。 思路：建铁路图，建公路图，从1到n分别BFS求最短路，如果其中一个不可达，输出-1，否则输出

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>a[405],b[405];
int c[405],d[405],x[405][405];
void bfs(int s,vector<int>g[],int f[]){
	for(int i=1;i<=n;i++)f[i]=1e9;
	queue<int>q;
	f[s]=0;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v:g[u]){
			if(f[v]==1e9){
				f[v]=f[u]+1;
				q.push(v);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		x[u][v]=x[v][u]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(x[i][j]){
				a[i].push_back(j);
				a[j].push_back(i);
			}else{
				b[i].push_back(j);
				b[j].push_back(i);
			}
		}
	}
	bfs(1,a,c);
	bfs(1,b,d);
	if(c[n]==1e9||d[n]==1e9)cout<<-1;
	else cout<<max(c[n],d[n]);
	return 0;
}

F.Valid BFS?

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5a5342cb1a32d5d51c4d61/problem/CF1037D 题意：给定一棵树和一个序列，判断该序列是否可能是从节点1开始的某次BFS遍历的输出顺序。BFS的特点：按层遍历，同层节点顺序任意 思路：给定一个序列，判断它是否可能是某个BFS的输出。 方法：按照序列中规定的顺序去模拟BFS，看能否完全匹配。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[200010]; 
int pos[200010];
bool cmp(int x,int y)
{
	return pos[x]<pos[y];
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int>a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		pos[a[i]]=i;
	}
	if(a[0]!=1){
		cout<<"No"<<endl;
		return 0;
	}
	int t=1;
	for(int i=0;i<n;i++){
		int u=a[i];
		vector<int>ch;
		for(int j=0;j<g[u].size();j++){
			int v=g[u][j];
			if(pos[v]>pos[u]){
				ch.push_back(v);
			}
		}
		sort(ch.begin(),ch.end(),cmp);
		for(int k=0;k<ch.size();k++){
			int c=ch[k];
			if(t>=n||a[t]!=c){
				cout<<"No";
				return 0;
			}
			t++;
		}
	}
	cout<<"Yes";
	return 0;
}