【模板】网络最大流

#include 
#include 
#include 
#include 

using namespace std;
const int maxM = 100005, maxN = 10005;
int N, M, S, T, ans;
struct Edge {
    int nxt, dis, to;
}e[maxM << 1]; int head[maxN], cnte = 1;
inline void add_Edge(int i, int j, int k) {
    e[++cnte].dis = k, e[cnte].nxt = head[i], e[cnte].to = j, head[i] = cnte;
}
int dep[maxN];
queue <int> q;
bool bfs() {
    memset(dep, 0, (N + 1) * sizeof(int));    
    q.push(S), dep[S] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int v, i = head[u]; i; i = e[i].nxt) {
            if(e[i].dis && !dep[v = e[i].to]) {
                dep[v] = dep[u] + 1, q.push(v);
            }
        }
    }
    return dep[T];
}
int dfs(int u, int in) {
    if(u == T) return in;
    int out = 0;
    for(int v, i = head[u]; i && in; i = e[i].nxt) {
        if(e[i].dis && dep[v = e[i].to] == dep[u] + 1) {
            int tmp = dfs(v, min(e[i].dis, in));
            e[i].dis -= tmp, e[i ^ 1].dis += tmp, in -= tmp, out += tmp;
        }
    }
    if(!out) dep[u] = 0;
    return out;  
}
int main() {
    scanf("%d%d%d%d", &N, &M, &S, &T);
    for(int i = 1, u, v, w; i <= M; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        add_Edge(u, v, w), add_Edge(v, u, 0);
    }
    while(bfs()) ans += dfs(S, 2e9);
    printf("%d\n", ans);
    return 0;
}