G : Maximum flow problem

Description

Give a directed graph of a network , Source point and sink point , Calculate its maximum flow . The number of vertices in the network is 1~N, The origin and destination are specified in the input .

Input

The first line gives four integers N(1 <= N <= 200), M(N <= M <= 5000),S,T, Indicates the number of nodes respectively 、 Number of directed edges 、 Source point serial number 、 Meeting point number .

Next M Each row contains three positive integers ui,vi,wi, It means the first one i The direction of a bar is from ui set out , arrive vi, The boundary right is wi.0<wi<=10000

Output

a line , Include a positive integer , Is the maximum flow of the network flow .

Sample Input

6 9 4 2
1 3 10
2 1 20
2 3 20
4 3 10
4 5 30
5 2 20
4 6 20
5 6 10
6 2 30

Sample Output

50

Hint

Statement of question ： Given a picture （n Nodes ,m side ）, Each side has a capacity , Now you need to remove some items from the node s（ It's called the source point ） Transport to node t（ It's called a meeting point ）, You can transfer from other nodes , Find the maximum transportation capacity .

Before introducing the solution to the maximum flow problem , First, I will introduce some concepts .

The Internet ： A network is a directed weighted graph , Contains a source point and a sink point , No reverse parallel edges .

Network flow ： Network flow is the flow on the network , Is defined in the network edge set E A nonnegative function on flow={flow（u,v）}, flow（u,v） Is the flow on the side .

Feasible flow ： A network flow that satisfies the following two properties flow It's called feasible flow .

Capacity constraints ： The actual flow on each side cannot exceed the changed maximum flow .

Conservation of flow ： Except for the source s And meeting point t outside , The inflow of all internal nodes is equal to the outflow .

Source point s： The source point is mainly outflow , But it may also flow into .

Net output value of the source point = The sum of outflow - The sum of inflows .

Confluence t： The meeting point is mainly inflow , But it may also flow out .

The net input value of the sink = The sum of inflows - The sum of outflow .

For a network feasible flow flow, Net output equals net input , This is still the conservation of flow .

Network maximum flow ： On the premise of satisfying capacity constraints and flow conservation , Find a network flow with the largest net output in the flow network .

Reverse arc ： If from u To v The capacity of the side of is c , There is flow on this side f Flow through （ Called positive arc ）, It's equivalent to v To u There is one with a capacity of 0 The edge of , Its flow is - f , This side is the reverse arc . The function of the reverse arc is mainly used to find the augmented path .

The meaning of reverse arc ： The function of reverse arc is to make the currently selected arc give up automatically when there is a better decision . The reason why the reverse arc has flow is that if the forward arc has just been selected , Next time if there is a better strategy to make this f Flow into the sink , You can select the reverse arc , Will flow f revoke .

Residual network ： Calculate the difference between capacity and flow on each side of the graph （ It is called residual capacity ）, You can get the residual network . Note that due to the existence of reverse edges , The number of edges in the residual network may reach twice the number of edges in the original graph .

Augmentation path ： Any one of the residual networks starts from s To t All the directed paths of the corresponding graph correspond to an augmented path in the original graph —— As long as the minimum value of all residues in the road is found d , Increase the flow on all corresponding edges d that will do , This process is called augmentation .

Maximum flow theorem ： If the augmentation path cannot be found on the residual network , The current flow is the maximum flow ; conversely , If the current flow is not the maximum flow , Then there must be an expansion path .

Two 、AC Code

#include <iostream>
#include <cstring>
#include<queue>

#include<vector>
using namespace std;
int n,m;
const int maxn=1005;
int g[maxn][maxn];// Capacity 
int f[maxn][maxn];// Traffic 
int vis[maxn];
int pre[maxn];// Array of precursors 
const int INF =1111111;

int bfs(int s,int t)
{
    
    memset(pre,-1,sizeof(pre));// Initialize array 
    memset(vis,0,sizeof(vis));

    queue<int > q;
    vis[s]=1;// Recording time 
    q.push(s);// Join the queue 
   // cout<<s<<t<<endl;

    while(!q.empty())
    {
    
        int now=q.front();
        q.pop();

        for(int i=1;i<=n;i++)
        {
    
            if(!vis[i]&&g[now][i])
            {
    

                vis[i]=1;
                pre[i]=now;
                if(i==t)return 1;// When you get to the end, you quit 
                q.push(i);


            }
        }
    }
    return 0;
}

 int u,v;
int EK(int s,int t)
{
    
    int maxflow=0;
   
    while(bfs(s,t))//bfs Find a path 
    {
    
        int d=INF;
        v=t;
        while(v!=s)// Use the precursor to reset to the original s, And find the minimum flow , Meet capacity constraints 
        {
    
            // Get precursor 
            u=pre[v];


            // Find the minimum capacity on the path 
            if(d>g[u][v])d=g[u][v];

            // Iterate forward 
            v=u;
        }

        maxflow+=d;// Maximum flow =+ Minimum capacity on all paths 
       // cout<<d<<endl;
        v=t;
        while(v!=s)
        {
    
            // Get precursor 
            u=pre[v];

            // Find the augmentation path 
            g[u][v]-=d;
            g[v][u]+=d;// Satisfy the flow constraint , The input and output streams are equal 
            if(f[v][u]>0)f[v][u]=-d;
            else f[u][v]+=d;

             // Iterate forward 
            v=u;
        }

    }
    //cout<<maxflow<<endl;;
    return maxflow;
}
int main()
{
    
    int s,t;
    while(cin>>n>>m>>s>>t)
    {
    
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int i=0;i<m;i++)
        {
    
            int u,v,w;
            cin>>u>>v>>w;
            g[u][v]+=w;
        }
        cout<<EK(s,t)<<endl;

    }
    return 0;
}