【BFS小技巧，魔改BFS】ABC254 E - Small d and k

向右看齐 2024-03-23 16:20 37阅读 0赞

**发现题目特殊的地方是k特别小**

**算了算爆搜好像能过，然后T了，不知道为什么T**

**后来发现原来是memset的时候超时了，但是每次BFS都要初始化数组，数组大小又不能变，怎么办呢**

**开个vector和pair就能解决了！**

[E - Small d and k (atcoder.jp)][E - Small d and k _atcoder.jp]

题意：

给定一张图，每个点的度数不超过3，对于每次询问x k求离结点x距离不超过k的结点下标的和是多少

![5e20e1a14d3f4a738798ceb4a285caa6.png][]

思路：

直接暴力

用vector<bool>和pair<int,int>优化BFS

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    queue<pair<int,int> > q;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int N,M,Q,u,v,tot=0,x,k;
    int head[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    int bfs(int u){
    	vector<bool> vis(N+1);
    	while(!q.empty()) q.pop();
    	int res=0;
    	q.push({u,0});
    	vis[u]=1;
    	while(!q.empty()){
    		pair<int,int> u=q.front();
    		q.pop();
    		if(u.second>k) continue;
    		else res+=u.first;
    		for(int i=head[u.first];~i;i=edge[i].next){
    			if(!vis[edge[i].to]){
    				vis[edge[i].to]=1;
    				q.push({edge[i].to,u.second+1});
    			}
    		} 
    	}
    	return res;
    }
    signed main(){
    	cin>>N>>M;
    	G_init();
    	for(int i=1;i<=M;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	cin>>Q;
    	while(Q--){
    		cin>>x>>k;
    		cout<<bfs(x)<<'\n';
    	}
    }

[E - Small d and k _atcoder.jp]: https://atcoder.jp/contests/abc254/tasks/abc254_e
[5e20e1a14d3f4a738798ceb4a285caa6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/d01dface645e49d38d017ae747f45aad.png