Cod sursă (job #753963)

#include <bits/stdc++.h>

using namespace std;

ifstream fin("mincut.in");
ofstream fout("mincut.out");

struct Edge {
  int to, rev, flow, cap;
};

int const NMAX = 1000;
int const MMAX = 5000;
int n, m;
int src, dest;
vector<Edge> g[1 + NMAX];
int rem[1 + NMAX], dist[1 + NMAX];

bool bfs() {
  for(int i = 1; i <= n; i++) {
    dist[i] = INT_MAX;
  }
  dist[src] = 0;
  queue<int> q;
  q.push(src);
  while(!q.empty()) {
    int from = q.front();
    q.pop();
    for(auto e : g[from]) {
      if(e.flow < e.cap && dist[e.to] == INT_MAX) {
        dist[e.to] = dist[from] + 1;
        q.push(e.to);
      }
    }
  }
  return (dist[dest] != INT_MAX);
}

int dfs(int from, int deltaFlow) {
  if(from == dest) {
    return deltaFlow;
  }
  for(int &i = rem[from]; i < g[from].size(); i++) {
    Edge &e = g[from][i];
    if(e.flow < e.cap && dist[e.to] == dist[from]+1) {
      int addFlow = dfs(e.to, min(deltaFlow, e.cap - e.flow));
      //cout << "(" << from << " " << e.to << " " << addFlow << ")\n";

      if(addFlow > 0) {
        e.flow += addFlow;
        Edge &rev = g[e.to][e.rev];
        rev.flow -= addFlow;
        return addFlow;
      }
    }
  }
  return 0;
}

int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 1; i <= n; i++) {
      rem[i] = 0;
    }
    int delta = dfs(src, INT_MAX);
    while(delta > 0) {
      ans += delta;
      delta = dfs(src, INT_MAX);
    }
  }
  return ans;
}

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int a, b, c; fin >> a >> b >> c;
    g[a].push_back({b, (int)g[b].size(), 0, c});
    g[b].push_back({a, (int)g[a].size()-1, 0, 0});
  }
  src = 1, dest = n;
  fout << dinic() << "\n";
  for(Edge e : g[src]) {
    if(e.flow > 0) {
      fout << src << " " << e.to << "\n";
    }
  }
}