1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define inf 1000000000 5 using namespace std; 6 int ans,tot,vert,edg,S,T,fr[100005],to[200005],nxt[200005],f[200005]; 7 int que[100005],dist[100005]; 8 bool inq[100005]; 9 void adde(int p,int q,int F)10 {to[tot]=q;f[tot]=F;nxt[tot]=fr[p];fr[p]=tot++;}11 bool bfs();12 int dfs(int,int);13 int main()14 {15     memset(fr,-1,sizeof(fr));16     scanf("%d%d%d%d",&vert,&edg,&S,&T);17     int p,q,w,i;18     for(i=1;i<=edg;i++)19     {20         scanf("%d%d%d",&p,&q,&w);21         adde(p,q,w); adde(q,p,0);22     }23     while(bfs()) ans += dfs(S,inf);24     printf("%d",ans);25     return 0;26  } 27  bool bfs()28  {29      memset(dist,0,sizeof(dist));30      int l=0,r=0,i,t,now;31      que[++r] = S; dist[S] = 1;32      while(l<r)33      {34          now = que[++l];35          if(now==T) return true;36          for(i=fr[now];i!=-1;i=nxt[i])37          {38              t = to[i];39              if(!dist[t]&&f[i])40              {41                  dist[t] = dist[now]+1;42                  que[++r] = t;43              }44         }45     }46     return false;47  }48  int dfs(int now,int maxx)49  {50      if(now==T) return maxx;51      int i,t,ret=0,ss;52      for(i=fr[now];i!=-1;i=nxt[i])53      {54          t = to[i];55          if(dist[t]==dist[now]+1&&f[i])56          {57              ss = dfs(t,min(maxx-ret,f[i]));58              ret+=ss;59              f[i] -= ss; f[i^1] += ss;60              if(ret==maxx) return maxx;61         }62     }63     return ret;64  }