RainFestival @ 2019-06-02 11:10:16
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
int n,m,s,t,dep[10005],ans;
std::vector<int> a[10005],b[10005],f[10005];
std::queue<int> q;
void add(int x,int y,int v)
{
a[x].push_back(y);
a[y].push_back(x);
b[x].push_back(v);
b[y].push_back(0);
f[x].push_back(a[y].size()-1);
f[y].push_back(a[x].size()-1);
}
int bfs(int s,int e)
{
for (int i=1;i<=n;i++) dep[i]=0;
q.push(s);dep[s]=1;
while (!q.empty())
{
int v=q.front();q.pop();
for (int i=0;i<a[v].size();i++)
if (b[v][i]>0&&!dep[a[v][i]])
{
dep[a[v][i]]=dep[v]+1;
q.push(a[v][i]);
}
}
if (dep[e]) return 1;
return 0;
}
int dfs(int v,int now,int e)
{
if (v==e||!now) return now;
int flow=0;
for (int i=0;i<a[v].size();i++)
if (b[v][i]&&dep[v]+1==dep[a[v][i]])
{
int k=dfs(a[v][i],std::min(now,b[v][i]),e);
b[v][i]=b[v][i]-k;
b[a[v][i]][f[v][i]]=b[a[v][i]][f[v][i]]+1;
now=now-k;
flow=flow+k;
}
return flow;
}
int dinic(int s,int t)
{
int sumflow=0;
while (bfs(s,t)) sumflow=sumflow+dfs(s,2000000000,t);
return sumflow;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++)
{
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
add(x,y,v);
}
int ans=dinic(s,t);
printf("%d\n",ans);
return 0;
}