```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10010, M = 200010, INF = 1e15;
struct edge
{
int ed;
int len;
int id;
};
vector <edge> e[N];
int n, m, S, T;
int dep[N], cur[N];
bool bfs()
{
memset(dep, -1, sizeof dep);
queue <int> q;
q.push(S);
dep[S] = 0;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = 0; i < e[t].size(); i = i + 1)
{
int ed = e[t][i].ed;
if (dep[ed] == -1 && e[t][i].len)
{
dep[ed] = dep[t] + 1;
q.push(ed);
}
}
}
memset(cur, 0, sizeof(cur));
return (dep[T] != -1);
}
int dfs(int st, int limit)
{
if (st == T)
return limit;
for (int i = cur[st]; i < e[st].size(); i = i + 1)
{
cur[st] = i; // 当前弧优化
int ed = e[st][i].ed;
if (dep[ed] == dep[st] + 1 && e[st][i].len)
{
int t = dfs(ed, min(e[st][i].len, limit));
if (t)
{
e[st][i].len -= t;
e[ed][e[st][i].id].len += t;
return t;
}
}
}
return 0;
}
int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = dfs(S, INF)) r += flow;
return r;
}
signed main()
{
cin >> n >> m >> S >> T;
while (m -- )
{
int st, ed, len;
cin >> st >> ed >> len;
int sti = e[st].size();
int edi = e[ed].size();
e[st].push_back((edge){ed, len, edi});
e[ed].push_back((edge){st, 0, sti});
}
cout << dinic();
return 0;
}
```
by AC_love @ 2023-09-27 12:55:52
@[AC_love](/user/186472) 这不太对吧，当前弧优化cur里面记录的应该是上一次走到的边的信息，你这每一次bfs都memset一遍有啥用啊
by Michael_Liu @ 2023-09-27 13:07:08
@[Michael_Liu](/user/750869) 没问题，当前弧优化是对于一次dfs的。
by 聊机 @ 2023-09-27 13:08:53
@[Michael_Liu](/user/750869) 草。難道沒有用嗎。
by Ranger_HoFr @ 2023-09-27 13:08:55
@[聊机](/user/290959) @[Ranger_HoFr](/user/455490) 当前弧优化肯定有用啊，我意思是他这个当前弧优化写的不太对吧
by Michael_Liu @ 2023-09-27 13:10:53
@[AC_love](/user/186472) 我之前学的时候还有一个无用点优化之类的，但是好像效果不明显，尤其是加了当前弧以后，就是如果从一个流不为0的点往出流发现返回的流是0，那么就把这个点标记成不可用，这样别的点就不会再调用这个点了
by 聊机 @ 2023-09-27 13:11:19
@[Michael_Liu](/user/750869) 都说了当前弧是对于一次dfs，你增广完一次不更新不就错了吗
by 聊机 @ 2023-09-27 13:12:02
@[聊机](/user/290959)
~~我开始仔细看他用的是vector，还好奇为啥每次都把cur设为0而不是每个节点对应的出边呢，后来才反应过来用vector的话0对应的就是每个结点的第一条出边~~
by Michael_Liu @ 2023-09-27 13:16:56
@[Michael_Liu](/user/750869) 呃呃确实我一般也不喜欢用vector。
by 聊机 @ 2023-09-27 13:17:58
@[聊机](/user/290959)
~~我平时用结构体是这样的：~~
```cpp
if(deep[t]!=-1){
for(int i=1;i<=n;i++)
{
cur[i]=head[i];
}
return 1;
}
```
~~我是智力障碍~~
by Michael_Liu @ 2023-09-27 13:18:17