Edmonds-Karp algorithm

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

const int N=510;
const int INF=1e9;

struct Node
{
    vector<int> adj;
    int parent;
} g[N];

int n, m, flow, augment;
int cap[N][N];
int s, t;

void bfs ()
{
    augment=0;
    for (int i=1;i<=n;i++) g[i].parent=0;
    g[s].parent=-1;

    queue<int> q, minCap;
    q.push(s);
    minCap.push(INF);

    while (!q.empty())
    {
        int v=q.front();
        int curCap=minCap.front();
        q.pop(); minCap.pop();

        for (int i=0;i<g[v].adj.size();i++)
        {
            int xt=g[v].adj[i];
            if (cap[v][xt]>0 && g[xt].parent==0)
            {
                q.push(xt);
                minCap.push(min(curCap, cap[v][xt]));
                g[xt].parent=v;
                if (xt==t) augment=min(curCap, cap[v][xt]);
            }
        }
    }

    if (augment>0)
    {
        int v=t;
        while (v!=s)
        {
            cap[g[v].parent][v]-=augment;
            cap[v][g[v].parent]+=augment;
            v=g[v].parent;
        }
    }
}

void EdmondsKarp ()
{
    s=1; t=n;

    do
    {
        bfs();
        flow+=augment;
    }
    while (augment);
}

int main()
{
    scanf ("%d%d", &n, &m);
    for (int i=0;i<m;i++)
    {
        int a, b, c;
        scanf ("%d%d%d", &a, &b, &c);
        g[a].adj.push_back(b);
        cap[a][b]=c;
    }

    EdmondsKarp();

    printf ("%d", flow);

    return 0;
}