huangx607087 @ 2019-07-31 22:38:08
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int n,m,s,t,A;
int e[350000],w[350000],nxt[350000];
int hd[150000],step[150000],q[950000];
int f=1,r=1;
bool BFS()
{
memset(step,-44,sizeof(step));
step[s]=0,q[1]=s;
while(f<=r)
{
int x=q[f++],k=hd[x];
while(k)
{
if(w[k]&&step[e[k]]<0)
{
step[e[k]]=step[x]+1;
q[++r]=e[k];
}
k=nxt[k];
}
}
if(step[t]>=0) return 1;
return 0;
}
int DFS(int now,int flow)
{
int tmp=flow;
if(now==t) return tmp;
int k=hd[now];
while(k)
{
if(tmp<1) break;
if(w[k]&&step[now]+1==step[e[k]])
{
int midd=DFS(e[k],min(w[k],tmp));
tmp-=midd,w[k]-=midd;
if(k%2) w[k-1]+=midd;
else w[k+1]+=midd;
}
k=nxt[k];
}
}
int main()
{
freopen("Z.hx902in","r",stdin);
freopen("B.hx902out","w",stdout);
int i,j,k=0;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[++k]=y;w[k]=z;nxt[k]=hd[x];hd[x]=k;
e[++k]=x;w[k]=0;nxt[k]=hd[y];hd[y]=k;
}
while(BFS()) A+=DFS(s,20011230);
printf("%d\n",A);
return 0;
}