Cod sursă (job #611874)

// PUSH RELABEL WITH MAXIMUM HEIGHT

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <fstream>
#define VMAX 1000

using namespace std;

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

int V, E, x, y;
int flow[VMAX][VMAX], capacity[VMAX][VMAX];
int height[VMAX], excess[VMAX];

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);

    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
}

void relabel(int u)
{
    int mn = INT_MAX;

    for (int i = 0; i < V; ++i)
        if (capacity[u][i] - flow[u][i] > 0) // positive residual capacity => is in G_f
        mn = min(mn, height[i]);

    if (mn < INT_MAX)
        height[u] = mn + 1;
}

void init()
{
    height[0] = V;
    excess[0] = INT_MAX;

    for (int u = 1; u < V; ++u)
        push(0, u);
}

int max_height_vertex()
{
    int mx = 0, index_max = -1;

    for (int i = 1; i < V - 1; ++i)
    {
        if (excess[i])
        {
            if (index_max == -1) mx = height[i], index_max = i;
            else if (height[i] > mx) mx = height[i], index_max = i;
        }
    }

    return index_max;
}

int max_flow()
{
    int u = max_height_vertex();

    while (u != -1)
    {
        bool pushed = false;

        for (int w = 0; w < V && excess[u]; ++w)
        {
            if (height[u] == height[w] + 1 && capacity[u][w] - flow[u][w] > 0)
                push(u, w), pushed = true;
        }

        if (!pushed)
            relabel(u);

        u = max_height_vertex();
    }

    int maximum = 0;
    for (int i = 0; i < V; ++i)
        maximum += flow[i][V - 1];
    return maximum;
}


/*vector <int> find_max_height_vertices()
{
    vector <int> max_height;

    for (int i = 1; i < V - 1; ++i)
    {
        if (excess[i] > 0)
        {
            if (!max_height.empty() && height[i] > height[max_height[0]])
                max_height.clear();
            if (max_height.empty() || height[i] == height[max_height[0]])
                max_height.push_back(i);
        }
    }

    return max_height;
}

int max_flow()
{
    vector <int> current = find_max_height_vertices();

    while (!current.empty())
    {
        for (int i:current)
        {
            bool pushed = false;
            for (int j = 0; j < V && excess[i]; ++j) {
                if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1)
                {push(i, j); pushed = true;}
            }
            if (!pushed)
            {
                relabel(i);
                break;
            }
        }
        current = find_max_height_vertices();
    }

    int maximum = 0;
    for (int i = 0; i < V; ++i)
        maximum += flow[i][V - 1];
    return maximum;
}*/


int main()
{
    fin >> V;

    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j) fin >> capacity[i][j];

    init();

    fout << max_flow();

    fin.close();
    fout.close();
    return 0;
}