Cod sursă (job #461652)

#include<bits/stdc++.h>
#define N 1010
using namespace std;


const int inf=1e9;
struct edge {
    int x,c,op;
};
vector<edge>V[N];
int n,m,d[N], nxt[N], rs;
queue<int>Q;

bool BFS(int x) {
    for (int i=0; i<=n; ++i) d[i]=-1;
    Q.push(x); d[x]=0;
    while (Q.size()) {
        int x=Q.front(); Q.pop();
        for (auto it:V[x]) {
            int y=it.x, c=it.c, op=it.op;
            if (d[y]==-1 && c>0) {
                d[y]=d[x]+1;
                if (y!=n) Q.push(y);
            }
        }
    }
    return (d[n]!=-1);
}

int DFS(int x,int flow) {
    if (x==n) return flow;
    for (; nxt[x]<V[x].size(); nxt[x]++) {
        int y=V[x][nxt[x]].x;
        int c=V[x][nxt[x]].c;
        int op=V[x][nxt[x]].op;
        if (d[y]==d[x]+1 && c>0) {
            int f2=DFS(y,min(c,flow));
            if (f2) {
                V[x][nxt[x]].c-=f2;
                V[y][op].c+=f2;
                flow-=f2;
                return f2;
            }

        }
    } return 0;
}

void Dinic(int s, int t)  {
    int blockflow=0;
    while (BFS(s)) {
        for (int i=0; i<=n; ++i) nxt[i]=0;
        while ((blockflow=DFS(s,inf))) {
            rs+=blockflow;
        }
    }

}

int main() {
    ifstream cin("push-relabel.in");
    ofstream cout("push-relabel.out");
    cin>>n;
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j) {
             int x,y,c; cin>>c; x=i; y=j;
             if (!c) continue;
             V[x].push_back({y,c,(int)V[y].size()});
             V[y].push_back({x,0,(int)V[x].size()-1});
    }
    Dinic(1,n);
    cout<<rs;

    return 0;
}