NUKIY BLOG

#include<bits/stdc++.h>
using namespace std;

const int N = 1010, M = 20010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;   // f[i]代表编号为i的边的capacity
int q[N], d[N], pre[N]; // 当前边的编号、走到这条边的路径中最小的权值（最大的可行流量）、当前边的前驱路径
bool st[N];             // 标记bfs过程中已经达到了的点，防止重复搜索


void add(int a, int b, int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;   // 构建正向边
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;   // 构建反向边
}

bool bfs(){
    int hh = 0, tt = 0;
    
    memset(st, false, sizeof st);
    
    q[0] = S, st[S] = true, d[S] = INF; // 添加编号为1的边，终点为S
    
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i]){
            int ver = e[i];
            if(!st[ver] && f[i]){   // 如果当前边的终点还没有到达过，且当前这条边的权值大于0
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if(ver == T)    return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int EK(){
    int r = 0;
    while(bfs()){   // 若当前残留网络中还可以找到增广路径，则累加到r中，并修改这条路径中正向边和反向边的权值
        r += d[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1]){  // 回溯
            f[pre[i]] -= d[T];
            f[pre[i] ^ 1] += d[T];
        }
    }
    return r;
}

int main(){
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    while (m --){
        int a, b, c;    cin>>a>>b>>c;
        add(a, b, c);
    }
    
    cout<<EK()<<endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 10010, M = 200010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs(){
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i]){
            int ver = e[i]; // 当前弧优化
            if(d[ver] == -1 && f[i]){
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T)    return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit){
    if(u == T)  return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i]){
            int t = find(ver, min(f[i], limit - flow));
            if(!t)  d[ver] = -1;
            f[i] -= t;f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic(){
    int r = 0, flow;
    while(bfs())    while(flow = find(S, INF))  r += flow;
    return r;
}

int main(){
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    while(m--){
        int a, b, c;    cin>>a>>b>>c;
        add(a, b, c);
    }
    
    cout<<dinic()<<endl;    
    return 0;
}