加“减优化”
by hyfhaha @ 2019-08-15 13:21:59
您确定您的dfs没问题?
by hyfhaha @ 2019-08-15 13:24:33
@[hyfhaha](/space/show?uid=58711) 能教我吗QAQ
by _gifbmp @ 2019-08-15 13:25:20
@[hyfhaha](/space/show?uid=58711) 窝看日报学的QwQ
by _gifbmp @ 2019-08-15 13:25:43
```cpp
int dfs(int u,int flow){ //dfs找最大流
if(u==T)return flow;
int ret=flow; //记录初始流量
for(int i=head[u];i!=-1;i=Next[i]){
if(ret<=0)break; //如果已经没流了就退出
int v=to[i];
if(cost[i]!=0&&level[u]+1==level[v]){
int k=dfs(v,min(cost[i],ret)); //把能流的都给下一个点
ret-=k;cost[i]-=k;cost[i^1]+=k; //边权更新,剩余流量更新
}
}
return flow-ret; //返回流出的流量
}
```
by hyfhaha @ 2019-08-15 13:27:05
减优化:
加在return前
```cpp
if(flow-ret==0)level[u]=-1;
```
by hyfhaha @ 2019-08-15 13:29:29
@[hyfhaha](/space/show?uid=58711) 谢谢QAQ
by _gifbmp @ 2019-08-15 13:31:51