如题,感觉在最短路唯一的情况下其实就是单路增广,还访问了很多无效节点
看起来好像还不如EK
求教时间复杂度
int dfs(int p,int fl)
{
if(p==t)
return fl;
if(fl==0 || vis[p])
return 0;
vis[p]=1;
int sfl=0;
for(int i=nhead[p];i && fl;i=e[i].next)
{
nhead[p]=i;
if(dis[e[i].v]==dis[p]+e[i].w && e[i].fl)
{
int dfl=dfs(e[i].v,min(fl,e[i].fl));
mxcst+=dfl*e[i].w;
sfl+=dfl;
fl-=dfl;
cg(i,dfl);
}
}
vis[p]=0;
return sfl;
}
为节约版面只放推流部分