Cod sursă (job #774977)

#include <bits/stdc++.h>

using namespace std;
ifstream in ("mincut.in");
ofstream out ("mincut.out");

const int V_MAX = 1000;
const int E_MAX = 5000;

const int myINF = 2e9;

int V, E;
struct MaxFlow {

    int source, sink;

    struct defEdge {
        int from, to;
        int cap;
    }; vector<defEdge> edges;
    defEdge makeEdge (int from, int to, int cap) {return {from, to, cap};}
    vector<int> flowGraph[1 + V_MAX];

    void add_edge (int a, int b, int this_cap) {
        flowGraph[a].push_back (edges.size ());
        edges.push_back (makeEdge (a, b, this_cap));
        flowGraph[b].push_back (edges.size ());
        edges.push_back (makeEdge (b, a, 0));
    }

    int dist[1 + V_MAX];
    void resetDist (void) {
       for (int node = 1; node <= V; node ++)
          dist[node] = myINF;
    }
    bool bfs (void) {
       dist[source] = 0;
       queue<int> q;
       q.push (source);
       while (!q.empty ()) {
          int node = q.front (); q.pop ();
          for (int index : flowGraph[node]) {
             int x = edges[index].to, cap = edges[index].cap;
             if (dist[x] == myINF && cap > 0) {
               dist[x] = dist[node] + 1;
               q.push (x);
             }
          }
       }
       return (dist[sink] != myINF);
    }

    int ptr[1 + V_MAX];
    void resetPtr (void) {
       for (int node = 1; node <= V; node ++)
          ptr[node] = 0;
    }
    int dfs (int root, int pushed) {
       if (root == sink)
         return pushed;
       for (int& i = ptr[root]; i < (int) flowGraph[root].size (); i ++) {
          int index = flowGraph[root][i];
          int node = edges[index].to, cap = edges[index].cap;
          if (dist[root] + 1 != dist[node] || cap == 0) continue;
          int flow = dfs (node, min (pushed, cap));
          if (flow == 0) continue;
          edges[index].cap -= flow;
          edges[index ^ 1].cap += flow;
          return flow;
       }
       return 0;
    }

    int solveFlow (void) {
       int totalFlow = 0;
       while (bfs ()) {
          int addFlow;
          do {
            addFlow = dfs (source, myINF);
            totalFlow += addFlow;
          }
          while (addFlow > 0);

          resetDist ();
          resetPtr ();
       }
       return totalFlow;
    }

    void printMinCut (void) {
       for (int i = 0; i < (int) edges.size (); i += 2) {
          int a = edges[i].from, b = edges[i].to;
          if (dist[a] != myINF && dist[b] == myINF)
            out << a << " " << b << "\n";
       }
    }
} MF;

int main()
{
   in >> V >> E;
   MF.source = 1, MF.sink = V;
   for (int i = 1; i <= E; i ++){
      int a, b, this_cap; in >> a >> b >> this_cap;
      MF.add_edge (a, b, this_cap);
   }
   out << MF.solveFlow () << "\n";
   MF.printMinCut ();

   return 0;
}