ford_folkerson.cpp

struct Edge {
  int to, cap, rev;
  Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};

void AddEdge(vector<vector<Edge>> &g, int from, int to, int cap) {
  int idx = g[to].size(), rev_idx = g[from].size();
  g[from].emplace_back(to, cap, idx);
  g[to].emplace_back(from, 0, rev_idx);
}

class FordFolkerson {
  vector<vector<Edge>> g_;
  vector<bool> used_;
  int DFS(int v, int t, int f) {
    if (v == t) {
      return f;
    }

    used_[v] = true;
    for (auto &edge : g_[v]) {
      if (used_[edge.to] || edge.cap <= 0) {
        continue;
      }

      int d = DFS(edge.to, t, f < 0 || f > edge.cap ? edge.cap : f);
      if (d > 0) {
        edge.cap -= d;
        g_[edge.to][edge.rev].cap += d;
        return d;
      }
    }
    
    return 0;
  }

 public:
  FordFolkerson(vector<vector<Edge>> &g): g_(g), used_(g_.size()) {}
  int operator()(int s, int t) {
    int flow = 0, f;
    while (true) {
      fill(used_.begin(), used_.end(), false);
      f = DFS(s, t, -1);
      if (f == 0) {
        return flow;
      }

      flow += f;
    }
  }
};

ford_folkerson_main.cpp

int main(int argc, char *argv[])
{
  int n, m, s, t;
  cin >> n >> m >> s >> t;

  vector<vector<Edge>> g(n);
  for (int i = 0; i < m; ++i) {
    int from, to, cap;
    cin >> from >> to >> cap;
    AddEdge(g, from, to, cap);
  }

  FordFolkerson f(g);
  cout << f(s, t) << '\n';
  return 0;
}

ford_folkerson_test.txt

5 7 0 4
0 1 10
0 2 2
1 2 6
1 3 6
3 2 3
3 4 8
2 4 5

// should out "11"