有几个非常容易拖慢的地方。
#### 1
```cpp
inline int dfs(int hao,int flow)
{
if(hao==t)return flow;
int rest=flow;
```
当 flow==0时也应该return。否则将会多拓展拓展不了的点。
#### 2
dfs内部,循环中,剩余流量为0就也该break。理由如上。
#### 3
dfs中要记录这个节点上一次访问到第几条边,不要重复访问,像我用vector定义边就这样的:
```cpp
long long dfs(int p,long long a)
{
if(p==t||a==0) return a;
long long f,flow=0;
for(int& i=cur[p];i<G[p].size();i++)
{
Edge& e=edges[G[p][i]];
if(w[e.to]==w[p]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
flow+=f;
a-=f;
edges[G[p][i]^1].flow-=f;
if(a==0) break;
}
}
return flow;
}
```
最重要就应该是这个点了。
~~我还是喜欢用STL~~
by 菡萏 @ 2021-05-07 13:54:25