Cod sursă (job #461633)

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

struct edge {
    int x,f,c,op;
};
int n,m,rs;
queue<int>Q;
vector<edge>V[N];
int viz[N], e[N];

bool BFS(int x) {
    for (int i=1; i<=n; ++i) viz[i]=-1;
    Q.push(x); viz[x]=0;
    while (Q.size()) {
        x=Q.front(); Q.pop();
        for (int i=0; i<V[x].size(); ++i) {
            auto it=V[x][i];
            if (it.c>it.f && viz[it.x]==-1) {
                viz[it.x]=x; e[it.x]=i;
                if (it.x!=n) Q.push(it.x);
            }
        }
    }
    return (viz[n]!=-1);
}

int main() {
    ifstream cin("mincut.in");
    ofstream cout("mincut.out");
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y,c;
        cin>>x>>y>>c;
        V[x].push_back({y,0,c,(int)V[y].size()});
        V[y].push_back({x,0,0,(int)V[x].size()-1});
    }

    while (BFS(1)) {
        for (auto it:V[n]) {
            if (viz[it.x]==-1 || V[it.x][it.op].c==V[it.x][it.op].f) continue;
            viz[n]=it.x; e[n]=it.op;
            int flow=1e9;
            for (int i=n; i!=1; i=viz[i]) {
                auto y=V[viz[i]][e[i]];
                flow=min(flow,y.c-y.f);
            }
            rs+=flow;
            if (!flow) continue;
            for (int i=n; i!=1; i=viz[i]) {
                auto x=V[viz[i]][e[i]];
                V[viz[i]][e[i]].f+=flow;
                V[i][x.op].f-=flow;
            }
        }
    }
    cout<<rs<<'\n';
    BFS(1);
    for (int i=1; i<=n; ++i) {
        for (auto it:V[i]) {
            if (viz[i]!=-1 && it.c==it.f && it.c!=0) cout<<i<<" "<<it.x<<'\n';
        }
    }

    return 0;
}