Cod sursă (job #199033)

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("push-relabel.in");
ofstream fout("push-relabel.out");

const int MAX_N = 1010;
const int INF = 1000000000;

int c[MAX_N][MAX_N];
int f[MAX_N][MAX_N];

int n, m, S, D;

vector<int> A[MAX_N];

int h[MAX_N];
int e[MAX_N]; //excess
int pt[MAX_N];
bool inq[MAX_N];

queue<int> Q;


void push(int s, int d) {
    int val =  min(c[s][d] - f[s][d], e[s]);
    e[d] += val;
    e[s] -= val;
    f[s][d] += val;
    f[d][s] -= val;
    if(!inq[d]) {
        Q.push(d);
        inq[d] = true;
    }
}

int hc[2 * MAX_N];

void gapoptimisation(int height) {
    for(int i = 1; i <= n; i++) {
        if(h[i] > height && h[i] <= n) {
            h[i] = n + 1;
        }
    }
}

void relabel(int nod) {
    int mm = 2 * n + 10;
    for(int vecin : A[nod]) {
        if(c[nod][vecin] > f[nod][vecin]) {
            mm = min(mm, h[vecin]);
        }
    }
    if(h[nod] != mm + 1) {
        hc[h[nod]]--;
        int old = h[nod];
        h[nod] = mm + 1;
        hc[h[nod]]++;
        if(!hc[old]) {
            gapoptimisation(old);
        }
    }
}

void discharge(int nod) {
    while(e[nod]) {
        int var = pt[nod];
        for(pt[nod]; pt[nod] < var + A[nod].size(); pt[nod]++) {
            int vec = A[nod][pt[nod] % A[nod].size()];
            if(c[nod][vec] > f[nod][vec] && h[nod] > h[vec]) {
                push(nod, vec);
            }
            if(!e[nod]) {
                break;
            }
        }
        if(e[nod]) {
            relabel(nod);
        }
    }
    pt[nod] = pt[nod] % A[nod].size();
}

int pushrelabel() {
    S = 1; 
    D = n;
    inq[S] = inq[D] = true;
    h[S] = n;
    e[S] = INF;
    for(auto it = A[S].begin(); it != A[S].end(); it++) {
        int vec = *it;
        if(c[S][vec] > f[S][vec]) {
            push(S, vec);
        }
    }

    while(!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        inq[nod] = false;
        discharge(nod);
    }
    return e[D];
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            fin >> c[i][j];
            if(c[i][j]) {
                A[i].push_back(j);
                A[j].push_back(i);
            }
        }
    }
    

    fout << pushrelabel();
    return 0;
}