1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 6 const int maxn=1e5+10; 7 const int maxe=4e5+10; 8 const int inf=0x3f3f3f3f; 9 10 queue <int> q; 11 int dis[maxn],n,m,s,t,cnt,ls[maxn],ans; 12 struct edge 13 { 14 int to,c,op,next; 15 }e[maxe]; 16 17 void add(int x,int y,int w) 18 { 19 e[++cnt]=(edge){y,w,cnt+1,ls[x]}; 20 ls[x]=cnt; 21 e[++cnt]=(edge){x,0,cnt-1,ls[y]}; 22 ls[y]=cnt; 23 } 24 25 bool bfs() 26 { 27 memset(dis,inf,sizeof(dis)); 28 while (!q.empty()) q.pop(); 29 q.push(s); 30 dis[s]=0; 31 while (!q.empty()) 32 { 33 int x=q.front(); q.pop(); 34 for (int i=ls[x];i;i=e[i].next) 35 { 36 int y=e[i].to; 37 if (e[i].c&&dis[y]>dis[x]+1) 38 { 39 dis[y]=dis[x]+1; 40 if (y==t) return 1; 41 q.push(y); 42 } 43 } 44 } 45 return 0; 46 } 47 48 int dfs(int x,int maxf) 49 { 50 if (x==t) return maxf; 51 int ret=0; 52 for (int i=ls[x];i;i=e[i].next) 53 { 54 int y=e[i].to; 55 if (e[i].c&&dis[y]==dis[x]+1) 56 { 57 int f=dfs(y,min(e[i].c,maxf-ret)); 58 if (!f) dis[y]=-1; 59 e[i].c-=f; 60 e[e[i].op].c+=f; 61 ret+=f; 62 if (ret==maxf) break; 63 } 64 } 65 return ret; 66 } 67 68 int dinic() 69 { 70 int flow=0; 71 while (bfs()) 72 ans+=dfs(s,inf); 73 return ans; 74 } 75 76 int main () 77 { 78 cin>>n>>m>>s>>t; 79 for (int i=1,x,y,w;i<=m;i++) 80 { 81 cin>>x>>y>>w; 82 add(x,y,w); 83 } 84 ans=dinic(); 85 cout<<ans; 86 }