@[Ted_hjl](/user/342868)
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
int e, v, nxt;
}edge[20005];
int n, m, s, t;
int cnt = 1, head[20005], dis[20005];
void add(int u, int v, int w)
{
cnt ++;
edge[cnt].e = v;
edge[cnt].v = w;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
bool bfs(int s, int t)
{
memset(dis, 0, sizeof(dis));
dis[s] = 1;
queue<int> que;
que.push(s);
while (!que.empty())
{
int r = que.front();
que.pop();
for (int i = head[r] ; i != -1 ; i = edge[i].nxt)
{
int j = edge[i].e;
if (!dis[j] && edge[i].v)
{
dis[j] = dis[r] + 1;
que.push(j);
}
}
}
if(dis[t])
{
return true;
}
else
{
return false;
}
}
int dfs(int u, int ed, int flo)
{
if (u == ed)
{
return flo;
}
int ans = 0;
for (int i = head[u] ; i != -1 ; i = edge[i].nxt)
{
int v = edge[i].e;
if (dis[v] == dis[u] + 1 && edge[i].v > 0)
{
int d = dfs(v, ed, min(flo - ans, edge[i].v));
edge[i].v -= d;
edge[i ^ 1].v += d;
ans += d;
}
}
if(ans == 0) dis[u] = 0;
return ans;
}
int dinic(int s, int t)
{
int ans = 0;
while (bfs(s, t))
{
ans += dfs(s, t, INT_MAX);
}
return ans;
}
signed main()
{
memset(head, -1, sizeof(head));
cin >> n >> m >> s >> t;
for (int i = 1 ; i <= m ; i ++)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
cout << dinic(s, t);
}
```
by Sharing666 @ 2022-02-11 19:42:48
@[Sharing666](/user/394991) 谢了
by qfpjm @ 2022-02-11 19:44:33
开 long long。
dfs 加上这一行优化：
```cpp
if(ans == 0) dis[u] = 0;
```
by Sharing666 @ 2022-02-11 19:44:51
@[Ted_hjl](/user/342868) 不用谢
by Sharing666 @ 2022-02-11 19:45:05