为什么bfs需要初始化队列
查看原帖
为什么bfs需要初始化队列
711031
suyi1111楼主2025/6/20 20:53

以下代码在删去主函数 while(1) 中的 Bfs_zy_dl = queue<int>();

会导致死循环TLE,为什么会导致这样呢?

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct edge{
	int u,v;
	int yt,xt;//原图,现图 
};
vector<int>out[30001];
edge e[30010];
int The_tot_of_e=1;
void add(int u,int v,int w){e[++The_tot_of_e]={u,v,w,w},out[u].push_back(The_tot_of_e),e[++The_tot_of_e]={v,u,0,0},out[v].push_back(The_tot_of_e);}
int n,m,s,t;
int sd[30001],dqh[30001];//深度,当前弧 
queue<int>Bfs_zy_dl;

void bfs(){
	memset(sd,0,sizeof sd);
	sd[s]=1;
	Bfs_zy_dl.push(s);
	while(!Bfs_zy_dl.empty()){
		int u=Bfs_zy_dl.front();
		Bfs_zy_dl.pop();
		for(int i:out[u]){
			if(sd[e[i].v]==0&&e[i].xt!=0){
				sd[e[i].v]=sd[u]+1;
				if(e[i].v==t)return; 
				Bfs_zy_dl.push(e[i].v);
			}
		}
	}
}
int dfs(int x,int y){
	if(x==t)return y;
	int ret=0;
	for(int i=dqh[x];i<out[x].size()&&y>0;i++){
		dqh[x]=i; 
		if(e[out[x][i]].xt==0){
			continue;
		}
        int v=e[out[x][i]].v;
        if(sd[v]==sd[x]+1){
            int mqs=dfs(v,min(y,e[out[x][i]].xt));
            if(!mqs)
                sd[v]=0;
            e[out[x][i]].xt-=mqs;
            e[out[x][i]^1].xt+=mqs;
            ret+=mqs;
            y-=mqs;
        }
	} 
	return ret;
}
main(){
	int The_ans=0;
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;add(u,v,w);
	}
	while(1){
		bfs();
		Bfs_zy_dl = queue<int>(); 
		if(sd[t]==0)break;
		memset(dqh,0,sizeof dqh);
		The_ans+=dfs(s,LONG_LONG_MAX-10000);
	}
	cout<<The_ans;
	return 0;
}
2025/6/20 20:53
加载中...