Cod sursă (job #131416)

#include <fstream>
#include <queue>
#include <iostream>

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 f;
    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;
            const int f = E[i].f;
            if(c == f || 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 - E[e].f;
        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].f += fmin;
        E[mate].f += 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();
}

int belong[MAX_N];


void minCut() {
    BFS();

    for(int i = 1 ; i <= n ; ++i) {
        if(viz[i])
            belong[i] = 1;
        else
            belong[i] = 2;
    }

    int dat = 0;

    for(int nod = 1 ; nod <= n ; ++nod) {
        for(int i = fst[nod] ; i != -1 ; i = E[i].next) {
            const int son = E[i].to;

            if(belong[nod] == belong[son])
                continue;

            if(E[i].c == 0)
                continue;

            out << nod << " " << son << "\n";

            dat += E[i].f;
        }
    }

    cout << dat << "\n";
}

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();

    return 0;
}