Cod sursă (job #189643)

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 800;
const int NIL = -1;
const int INF = numeric_limits <int> :: max();

struct Edge
{
    int v;
    int cap;
    int next;
};

Edge G[MAX_N * MAX_N];
int head[MAX_N];
int D[MAX_N];
int F[MAX_N + 1];

int ptr[MAX_N];
int father[MAX_N];
int currentPointer[MAX_N];

int Q[MAX_N];
int qStart, qEnd;

void addEdge(int u, int v, int cap, int pos)
{
    G[pos] = { v, cap, head[u] };
    head[u] = pos;
}

int main()
{
    ifstream in("push-relabel.in");
    in.tie(0);
    ios_base::sync_with_stdio(false);

    int N;
    int z = 0;

    in >> N;

    memset( head, NIL, 4 * N );

    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < N; j++ )
        {
            int cap;

            in >> cap;

            if ( i != j )
                addEdge( i, j, cap, z++ );
        }

    in.close();

    // ISAP

    Q[0] = N - 1;
    qStart = 0;
    qEnd = 1;
    D[N - 1] = 1;

    while ( qStart != qEnd )
    {
        int u = Q[qStart++];

        for ( int i = head[u]; i != NIL; i = G[i].next )
        {
            int v = G[i].v;

            if ( D[v] == 0 )
            {
                D[v] = D[u] + 1;
                Q[qEnd++] = v;
            }
        }
    }

    for ( int i = 0; i < N; i++ )
        F[ D[i] ]++;

    memmove( currentPointer, head, 4 * N );

    int flow = 0;
    int u = 0;

    while ( D[u] <= N )
    {
        if ( u == N - 1 )
        {
            int minFlow = INF;

            while ( u != 0 )
            {
                minFlow = min( minFlow, G[ ptr[u] ].cap );
                u = father[u];
            }

            u = N - 1;

            while ( u != 0 )
            {
                G[ ptr[u] ].cap     -= minFlow;
                G[ ptr[u] ^ 1 ].cap += minFlow;
                u = father[u];
            }

            u = 0;

            flow += minFlow;
        }

        int i = currentPointer[u];

        while ( ( i != NIL ) && ( !G[i].cap || D[u] != D[ G[i].v ] + 1 ) )
            i = G[i].next;

        if ( G[i].cap > 0 && D[u] == D[ G[i].v ] + 1 )
        {
            ptr[ G[i].v ] = i;
            father[ G[i].v ] = u;
            currentPointer[u] = i;

            u = G[i].v;
        }
        else
        {
            int T = N;

            for ( i = head[u]; i != NIL; i = G[i].next )
                if ( G[i].cap > 0 )
                    T = min( T, D[ G[i].v ] );

            F[ D[u] ]--;

            if ( !F[ D[u] ] )
                break;

            D[u] = T + 1;

            F[ D[u] ]++;
            currentPointer[u] = head[u];

            if ( u != 0 )
                u = father[u];

        }
    }

    ofstream out("push-relabel.out");
    out << flow << '\n';
    out.close();
    return 0;
}