以下代码在删去主函数 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;
}