Cod sursă (job #137125)

#include <stdio.h>
#define MAXN 800

using namespace std;
FILE *in, *out;
int n, h[MAXN], e[MAXN], cf[MAXN][MAXN], start;
short current[MAXN];
struct vertex
{
    short v;
    short next;
    short prev;
}q[MAXN];

int valmin(int a, int b)
{
    if(a<b)
        return a;
    return b;
}

void init()
{
    int vol;
    h[0]=n;
    for(int i=0; i<n; i++)
    {
        vol=cf[0][i];
        cf[0][i]=-vol;
        cf[i][0]=vol;
        e[i]=vol;
        e[0]-=vol;
    }

}

void push(int u, int v)
{
    int vol = valmin(cf[u][v], e[u]);
    cf[u][v]-=vol;
    cf[v][u]+=vol;
    e[u]-=vol;
    e[v]+=vol;
}

void relabel(int u)
{
    int vmin=3*n;
    for(int i=0; i<n; i++)
        if(h[i]<vmin && cf[u][i]>0)
            vmin=h[i];
    h[u]=vmin+1;
}

void discharge(int v)
{
    while(e[v]>0)
    {
        int i=current[v];
        if(cf[v][i]>0 && h[v]==h[i]+1)
            push(v, i);
        else
            if(i<n-1)
                current[v]++;
            else
            {
                current[v]=0;
                relabel(v);
            }
    }
}

int main()
{
    in = fopen("push-relabel.in", "r");
    out = fopen("push-relabel.out", "w");
    start=0;
    fscanf(in, "%d", &n);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            fscanf(in, "%d", &cf[i][j]);
    init();
    for(int i=0; i<n-2; i++)
    {
        q[i].v=i+1;
        q[i].next=i+1;
        q[i].prev=i-1;
    }
    q[n-2].next=-1;
    int k=start, v=q[k].v;
    while(k!=-1)
    {
        int old_height=h[v];
        discharge(v);
        if(h[v]>old_height && start!=k)
        {
                q[q[k].prev].next=q[k].next;
                q[k].next=start;
                start=k;
                v=q[start].v;
        }
        else
        {
            k=q[k].next;
            v=q[k].v;
        }
    }
    fprintf(out, "%d", -1*e[0]);

    return 0;
}