Cod sursă (job #173310)

#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 810
using namespace std;
int capacity[MAXN][MAXN],flow[MAXN][MAXN],source,sink,excess[MAXN],n,in_queue[MAXN],height[MAXN],frequency[MAXN],last[MAXN];
queue<int> q;
int minim(int a,int b){
    if(a<b)
        return a;
    return b;
}
void push(int from,int to){
    int delta;
    if(height[from]>height[to]){
        delta=minim(capacity[from][to]-flow[from][to],excess[from]);
        if(delta==0)
            return;
        if(in_queue[to]==0){
            in_queue[to]=1;
            q.push(to);
        }
        excess[from]-=delta;
        excess[to]+=delta;
        flow[from][to]+=delta;
        flow[to][from]-=delta;
    }
}
void relabel(int node){
    int min_height=20000000,i;
    for(i=1;i<=n;i++)
        if(capacity[node][i]-flow[node][i]>0)
            min_height=minim(min_height,height[i]);
    frequency[height[node]]--;
    if(frequency[height[node]]==0)
        for(i=1;i<=n;i++)
            if(height[i]>height[node])
                height[i]=n+1;
    height[node]=min_height+1;
    frequency[height[node]]++;
}
void discharge(int node){
    while(excess[node]>0){
        push(node,last[node]);
        last[node]++;
        if(last[node]==n+1){
            last[node]=1;
            relabel(node);
        }
    }
    last[node]=(last[node]-1+n)%n;
    if(last[node]==0)
        last[node]=n;
}
int push_and_relabel(){
    int i,node;
    for(i=1;i<=n;i++)
        excess[source]+=capacity[source][i];
    height[source]=n+1;
    frequency[n+1]=1;
    frequency[0]=n-1;
    in_queue[source]=1;
    in_queue[sink]=1;
    for(i=1;i<=n;i++)
        push(source,i);
    while(!q.empty()){
        node=q.front();
        q.pop();
        in_queue[node]=0;
        discharge(node);
    }
    return excess[sink];
}
int main(){
    freopen("push-relabel.in","r",stdin);
    freopen("push-relabel.out","w",stdout);
    int i,j;
    scanf("%d",&n);
    source=1;
    sink=n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&capacity[i][j]);
    printf("%d",push_and_relabel());
    return 0;
}