ford

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector< vector <int> > matrix; //пропускная способность(наличие ребра)
vector<int> S;//множество вершин Si

vector<bool> used;
vector<int> metka;
vector<int> way;

int head;
int F;
int iteration=0;
const int super_metka=-14567;
void start1()
{

    used[0]=true;
    metka[0]=0;
    way[0]=-1;
    for(size_t i=1;i<head;i++)
    {
        used[i]=false;
        metka[i]=0;
        way[i]=-1;
    }
}

int bfs(int start,int end)  //конец не учёл!!(шаг 2,6)
{
    queue<int> turn; //очередь с номерами вершин
    start1();

    turn.push(start); //начало итерации, первая вершина
    int j=0;

    while(j!=end)
    {
        int turn_tail=turn.front();
        //if(iteration==2)
        //cout<<turn.front()<<' ';
        turn.pop();
        //if(iteration==2)
        //cout<<turn.front();
        int max=0;
        //if(iteration==2)
        //cout<<turn.front()<<' '<<turn_tail<<endl;;
        for(size_t i=0;i<matrix[turn_tail].size();i++)
        {
            if(matrix[turn_tail][i]!=0 && !used[i] &&
                                        matrix[turn_tail][i]>max)
            {
              max=matrix[turn_tail][i];
              j=i;
              //if(iteration==2)
                //cout<<max<<' '<<j;
            }
        }

        if(max==0 && turn_tail==0)
            return 0;

        if(max==0 && turn_tail!=0)
        {//шаг 4, удаление;есть сомнения

            metka[j]=super_metka;
            int smth=way[j];
            way[j]=-1;
            j=smth;

            turn.push(j);
          //cout<<turn.front()<<endl;
        }
        else{

        turn.push(j);
        used[j]=true;

        metka[j]=max;

        way[j]=turn_tail;
        //if(iteration==2){
        //for(int i=0;i<5;i++)
          //  cout<<way[i]<<' ';
          //  cout<<endl;
    //}
        }
       // if(iteration==2)
         //   cout<<j<<endl;
    }
    iteration++;
    /*if(iteration==3)
    {
        for(int i=0;i<5;i++)
            cout<<metka[i]<<' ';
    }*/
    /*if(iteration==3){
        for(int i=0;i<5;i++)
            cout<<way[i]<<' ';
    }*/
    if(j!=0)
        return 1;
    return 0;
}

int min()
{
    int min=5000;
    /*if(iteration==3){
    for(size_t i=0;i<head;i++)
    {
        cout<<metka[i]<<' ';
    }
    }*/
    for(size_t i=0;i<head;i++)
    {
        if(metka[i] && metka[i]<min && metka[i]!=super_metka){
            min=metka[i];

        }
    }
    //cout<<min<<endl;
    return min;
}
/*void Vivod()
{
    cout<<endl;

    for(int j=0;j<5;j++)
            for(int i=0;i<5;i++)
            {
                cout<<matrix[j][i]<<' ';
                if(i+1==5)
                    cout<<endl;
            }
}
*/

void max_flow(int start,int end)
{

    while(bfs(0,1)) //итерации(пока существует путь)
    {
      int fp=min();
      F+=fp;

      for(int i=0;i<end+1;i++)
      {
        if(way[i]!=-1)
        {

            matrix[way[i]][i]-=fp;
            matrix[i][way[i]]+=fp;



        }
      }

    }
    cout<<"max flow="<<F<<endl;
}


int main()
{
    int n;
    freopen ("data.txt", "r", stdin);
    cin>>n;
    head=n;
    used.reserve(n+1);
    metka.reserve(n+1);
    way.reserve(n+1);
    for(size_t i=0;i<n;i++)
    {
        vector<int> temp;
        for(size_t j=0;j<n;j++)
        {
            int trash;
            cin>>trash;
            temp.push_back(trash);
        }
        matrix.push_back(temp);
    }

    max_flow(0,n-1);
}