Cod sursă (job #131075)

#include <fstream>
#include <queue>

using namespace std;

const int MAX_N = 1000 + 1;
const int MAX_M = 5000 + 1;
const int INF = (1 << 30) - 1;
ofstream out("mincut.out");

struct edge {
    int to;
    int c;
    int next;
    int mate;
};

edge E[MAX_M * 2];
int at;

int fst[MAX_N];

int n, m;

int addEdge(const int from, const int to, const int c) {
    E[at].to = to;
    E[at].c = c;
    E[at].next = fst[from];
    fst[from] = at;
    return at++;
}

queue<int> Q;
bool viz[MAX_N];
int TT[MAX_N];
int ch[MAX_N];

bool BFS() {
    for(int i = 1 ; i <= n ; ++i) {
        viz[i] = 0;
        TT[i] = 0;
        ch[i] = 0;
    }

    Q.push(1);
    viz[1] = 1;

    while(!Q.empty()) {
        const int nod = Q.front();
        Q.pop();

        if(nod == n)
            continue;

        for(int i = fst[nod] ; i != -1 ; i = E[i].next) {
            const int son = E[i].to;
            const int c = E[i].c;
            if(c == 0 || viz[son])
                continue;

            viz[son] = 1;
            TT[son] = nod;
            ch[son] = i;
            Q.push(son);
        }
    }

    return viz[n];
}

int maxflow;

void backtrace(const int st) {
    int fmin = INF;
    int now = st;
    while(now != 1) {
        if(!viz[now])
            return;
        int e = ch[now];
        int fnow = E[e].c;
        if(fnow < fmin)
            fmin = fnow;

        now = TT[now];
    }

    if(!fmin)
        return;

    now = st;

    while(now != 1) {
        int e = ch[now];
        int mate = E[e].mate;
        E[e].c -= fmin;
        E[mate].c += fmin;

        now = TT[now];
    }

    maxflow += fmin;
}

void addFlow() {
    for(int i = fst[n] ; i != -1 ; i = E[i].next) {
        TT[n] = E[i].to;
        ch[n] = E[i].mate;
        if(viz[TT[n]])
            backtrace(n);
    }
}

void flow() {
    while(BFS())
        addFlow();
}

void minCut() {
    Q.push(1);
    int nod;
    for(int i = 1 ; i <= n; ++i)
        viz[i] = 0;
    viz[1] = 1;

    while(!Q.empty()) {
        nod = Q.front();
        Q.pop();
        for(int i = fst[nod] ; i != -1 ; i = E[i].next) {
            if(E[i].c == 0) {
                out << nod << " " << E[i].to << "\n";
            } else if(!viz[E[i].to]) {
                viz[E[i].to] = 1;
                Q.push(E[i].to);
            }
        }
    }
}

int main() {
    ifstream in("mincut.in");
    in >> n >> m;
    int x, y, c;

    int a, b;

    for(int i = 1 ; i <= n ; ++i)
        fst[i] = -1;

    for(int i = 1 ; i <= m ; ++i) {
        in >> x >> y >> c;
        a = addEdge(x, y, c);
        b = addEdge(y, x, 0);

        E[a].mate = b;
        E[b].mate = a;
    }
    in.close();

    flow();


    out << maxflow << "\n";

    minCut();
}