rt,用的Dinic,写了调试代码,发现是bfs一直等于true
求助!
#include<bits/stdc++.h>
using namespace std;
const int N=205,mx=0x3f3f3f3f;
int n,m,s,t,ans,dis[N];
struct Node
{
int to,w;
};
vector<Node>nbr[N];
bool bfs()
{
queue<int>q;
memset(dis,0x3f,sizeof dis);
int cur=s;
q.push(cur);
dis[s]=0;
while(!q.empty())
{
cur=q.front();
q.pop();
for(int i=0;i<nbr[cur].size();i++)
{
int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
if(dis[nxt]==mx&&w>0)
{
q.push(nxt);
dis[nxt]=dis[cur]+1;
if(nxt==t)
return true;
}
}
}
return false;
}
int dfs(int x,int sum)
{
if(x==t)
return sum;
int num=0;
for(int i=0;i<nbr[x].size();i++)
{
int nxt=nbr[x][i].to,w=nbr[x][i].w;
if(dis[x]+1==dis[nxt]&&w>0)
{
int val=dfs(nxt,min(sum,w));
nbr[x][nxt].w-=val;
nbr[nxt][x].w+=val;
num+=val;
sum-=val;
}
}
return num;
}
int main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
int x,y,w;
cin>>x>>y>>w;
nbr[x].push_back((Node){y,w});
nbr[y].push_back((Node){x,0});
}
while(bfs()==true)
{
ans+=dfs(s,mx);
}
cout<<ans;
return 0;
}