#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mp(x,y) make_pair(x,y)
using namespace std;
template<typename xxx>void read(xxx &x)
{
x=0;int f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;
}
template<typename xxx>void print(xxx x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int maxn=200002;
const int inf=0x7fffffff;
int n,m,s,t,maxflow;
struct edge{
int to,last,val;
}e[maxn];
int head[maxn],tot;
inline void add(int from,int to,int val)
{
tot++;
e[tot].to=to;
e[tot].val=val;
e[tot].last=head[from];
head[from]=tot;
}
queue<int>q;
int vis[maxn];
int rem[maxn];//剩余流量
int pre[maxn];
inline int bfs()//用来寻找s,t的最短路并记录,如果s,t不连通则返回0
{
while(q.size()) q.pop();
memset(vis,0,sizeof(vis));//当次增广路不能走重点，但每次增广路互不影响
q.push(s);vis[s]=1;
rem[s]=inf;
while(q.size())
{
int x=q.front();q.pop();
for(rint i=head[x];i;i=e[i].last)
{
if(e[i].val)//忽略流量为零
{
int y=e[i].to;
if(vis[y]) continue;//保证去了的点不在去，也保证下两句正确性
rem[y]=min(rem[x],e[i].val);//到达y时最小剩余流
pre[y]=i;//连向y的边的编号
q.push(y),vis[y]=1;
if(y==t) return 1;//连通肯定能找到t
}
}
}
return 0;
}
inline void update()//更新最短路与反向边优化
{
int x=t;
while(x!=s)
{
int i=pre[x];
e[i].val-=rem[t];
e[i^1].val+=rem[t];
x=e[i^1].to;
}
maxflow+=rem[t];
}
int main()
{
tot=1;//方便正反边转换
read(n);read(m);read(s);read(t);
for(rint i=1;i<=m;i++)
{
int a,b,c;
read(a);read(b);read(c);
add(a,b,c);add(b,a,0);
}
while(bfs())
update();
print(maxflow);
}
/*
网络流学习
1，通过流量不超过容量
2,除源点汇点外其余点流入流出量相同
3，每条边正反方向流量大小相同方向相反
4，剩余流量为容量减去当前流量
5，最大流的值等于最小割的容量
最小割：就是给你一个图，然后给你边权，问你如何在割掉的边权尽量小的情况下把指定的两个点or两个集合分开
选出一些管道，切断以后，图不连通，这些管道的集合就叫割。这些边的容量之和叫做这个割的容量。
推论 任意一个流都小于等于任意一个割
考虑FF算法时，残量网络上没有了增广路。
那么我们假设这时候，从源点经过残量网络能到达的点组成的集合为X，不能到达的点为Y。显然汇点在Y里，并且残量网络上没有从X到Y的边。
可以发现以下事实成立：
1.Y到X的边的流量为0.如果不为0，那么一定存在一条从X到Y的反向边，于是矛盾。
2.X到Y的边流量等于其容量。只有这样它才不会在残量网络中出现。
■根据第一个条件得知：没有流量从X到Y后又回到X。所以当前流量应该等于从X到Y的边的流量之和，而根据第二个条件他又等于X到Y的边容量之和。
■而所有从X到Y的边又构成了一个割，其容量等于这些边的容量之和。
★这意味着我们找到一个割和一个流，使得前者的流量等于后者的容量。而根据前边的结论，最大流的流量不超过这个割的容量，所以这个流一定是最大流。
■同样的，最小割的容量也不会小于这个流的流量，所以这个割也一定是最小割。
■而这也正是FF方法的最后局面，由此我们对出结论：FF是正确的，并且最小割等于最大流
6，最大流等于二分图最大匹配数
7，残量网络=容量网络-流量网络
8，增广路EK算法（FF思想） 十万以内
若一条s到t的路径上所有边都有剩余流量，则该路还可以增加新流量，EK是使用bfs不断找增广路直到没有
每次bfs一条s到t的路径，计算路径上最小值，加入总流量中
将增广路上所有边的残量减去v，反向边的残量加上v。
建反向边，留下一个标记，让后面的流有机会让前面的流走另一条路，给程序有反悔的机会，这样再次从反向边流过就相当于抵消了。。
每条边代表着一个里面流动着不可压缩流体的具有流速限制的管道, 那么反向增广就有点像是反向加压来尝试把流体压回原来的点, 总的效果就是让这条边里的流速减缓或反向, 而让流返回原来的点重新决策.
n*m*m(n为点，m为边)，边少时用
*/ 
投递金山WPS等公司10个岗位 >