Cod sursă (job #136975)

#include <stdio.h>
#define MAXN 800

using namespace std;
FILE *in, *out;
int n, c[MAXN][MAXN], h[MAXN], e[MAXN], f[MAXN][MAXN], start;
short current[MAXN];
struct vertex
{
    short v;
    short next;
}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=c[0][i];
        f[0][i]=vol;
        f[i][0]=-vol;
        e[i]=vol;
        e[0]-=vol;
    }

}

void push(int u, int v)
{
    int vol = valmin(c[u][v], e[u]);
    f[u][v]+=vol;
    f[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 && f[u][i]<c[u][i])
            vmin=h[i];
    h[u]=vmin+1;
}

void discharge(int v)
{
    while(e[v]>0)
    {
        int i=current[v];
        if(c[v][i]>0 && h[v]==h[i]+1)
            push(v, i);
        else
            if(i<n)
                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", &c[i][j]);
    init();
    for(int i=0; i<n-2; i++)
    {
        q[i].v=i+1;
        q[i].next=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)
        {
             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;
}