1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4 const int maxn=5005;

 5 const int inf=0x3f3f3f3f;

 6 int tot,n,m,s,t,x,y,z,d[maxn];

 7 int adj[maxn],nex[maxn<<1],to[maxn<<1],w[maxn<<1],flow[maxn<<1];

 8 void add(int x,int y,int z){

 9     nex[tot]=adj[x];

10     adj[x]=tot;

11     to[tot]=y;

12     w[tot]=z;

13     flow[tot++]=0;

14 }

15 bool bfs(){

16     memset(d,0,sizeof(d));

17     queue<int> q;

18     d[s]=1;

19     q.push(s);

20     while(!q.empty()){

21         int u=q.front();

22         q.pop();

23         for(int i=adj[u];~i;i=nex[i]){

24             int v=to[i];

25             if(!d[v]&&w[i]>flow[i]){

26                 d[v]=d[u]+1;

27                 q.push(v);

28                 if(v==t) return 1;

29             }

30         }

31     }

32     return 0;

33 }

34 int dfs(int u,int fw){

35     if(u==t) return fw;

36     int rest=fw;

37     for(int i=adj[u];~i&&rest;i=nex[i]){

38         int v=to[i];

39         if(d[v]==d[u]+1&&w[i]>flow[i]){

40             int k=dfs(v,min(rest,w[i]-flow[i]));

41             if(!k) d[v]=0;

42             flow[i]+=k;

43             flow[i^1]-=k;

44             rest-=k;

45         }

46     }

47     return fw-rest;

48 }

49 int dinic(){

50     int maxflow=0;

51     while(bfs()){

52         //for(int i=1;i<=n;i++)

53         maxflow+=dfs(s,inf);

54     }

55     return maxflow;

56 }

57 signed main()

58 {

59     cin>>n>>m>>s>>t;

60     memset(adj,-1,sizeof(adj));

61     for(int i=1;i<=m;i++){

62         cin>>x>>y>>z;

63         add(x,y,z);add(y,x,0);

64     }

65     cout<<dinic();

66     return 0;

67 }

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=5005;

const int inf=0x3f3f3f3f;

int tot,n,m,s,t,x,y,z,d[maxn],now[maxn];

int adj[maxn],nex[maxn<<1],to[maxn<<1],w[maxn<<1],flow[maxn<<1];

void add(int x,int y,int z){

    nex[tot]=adj[x];

    adj[x]=tot;

    to[tot]=y;

    w[tot]=z;

    flow[tot++]=0;

}

bool bfs(){

    memset(d,0,sizeof(d));

    queue<int> q;

    d[s]=1;

    q.push(s);

    for(int i=1;i<=n;i++)

        now[i]=adj[i];

    while(!q.empty()){

        int u=q.front();

        q.pop();

        for(int i=adj[u];~i;i=nex[i]){

            int v=to[i];

            if(!d[v]&&w[i]>flow[i]){

                d[v]=d[u]+1;

                q.push(v);

                if(v==t) return 1;

            }

        }

    }

    return 0;

}

int dfs(int u,int fw){

    if(u==t) return fw;

    int rest=fw;

    for(int i=now[u];~i&&rest;i=nex[i]){

        int v=to[i];

        if(d[v]==d[u]+1&&w[i]>flow[i]){

            int k=dfs(v,min(rest,w[i]-flow[i]));

            if(!k) d[v]=0;

            flow[i]+=k;

            flow[i^1]-=k;

            rest-=k;

        }

    }

    return fw-rest;

}

int dinic(){

    int maxflow=0;

    while(bfs()){

        //for(int i=1;i<=n;i++)

        maxflow+=dfs(s,inf);

    }

    return maxflow;

}

signed main()

{

    cin>>n>>m>>s>>t;

    memset(adj,-1,sizeof(adj));

    for(int i=1;i<=m;i++){

        cin>>x>>y>>z;

        add(x,y,z);add(y,x,0);

    }

    cout<<dinic();

    return 0;

}