#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
const int INF = 1e9;
int n, **a;
void read()
{
    cout << "Введите N:";
    cin >> n;
    a = new int*[n+1];


    for (int i = 0; i<=n; i++)
    {
        a[i] = new int[n+1];
        for (int j = 0; j<=n; j++)
            a[i][j] = 0;
    }
    cout << "Введите матрицу заработных плат NxN:";
    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=n; j++)
            cin >> a[i][j];


}
bool readfromfile()
{
    cout << "Введите путь к файлу: ";
    string s;
    cin >> s;
    ifstream fin(s);
    if (!(fin >> n))
        return false;
    a = new int*[n+1];


    for (int i = 0; i<=n; i++)
    {
        a[i] = new int[n+1];
        for (int j = 0; j<=n; j++)
            a[i][j] = 0;
    }

    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=n; j++)
        if (!(fin >> a[i][j]))
            return false;

    return true;
}
int Hungop;
vector<int> HungarianAlgo(int n, int **a)
{
    int m = n;
    vector<int> u (n+1), v (m+1), p (m+1), way (m+1);
    Hungop+=n+1;
    Hungop+=m+1;
    Hungop+=m+1;
    Hungop+=m+1;
    for (int i=1; i<=n; ++i)
    {
        p[0] = i;
        Hungop++;
        int j0 = 0;
        Hungop++;
        vector<int> minv (m+1, INF);
        Hungop+=m+1;
        vector<char> used (m+1, false);
        Hungop+=m+1;
        do {
            used[j0] = true;
            Hungop++;
            int i0 = p[j0],  delta = INF,  j1 = 0;
            Hungop+=3;
            for (int j=1; j<=m; ++j)
            {
                Hungop++;
                if (!used[j]) {
                    int cur = a[i0][j]-u[i0]-v[j];
                    Hungop+=2;
                    Hungop++;
                    if (cur < minv[j])
                    {
                        minv[j] = cur,  way[j] = j0;
                        Hungop+=2;
                    }
                    Hungop++;
                    if (minv[j] < delta)
                    {
                        Hungop+=2;
                        delta = minv[j],  j1 = j;
                    }
                }
            }
            for (int j=0; j<=m; ++j)
            {
                Hungop++;
                if (used[j])
                {
                    Hungop+=2;
                    u[p[j]] += delta,  v[j] -= delta;
                }
                else
                {
                    Hungop++;
                    minv[j] -= delta;
                }
            }
            j0 = j1;
            Hungop++;
        }
        while (p[j0] != 0);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
            Hungop+=3;
        } while (j0);
    }
    vector<int> ans (n+1);
    Hungop+=n+1;
    for (int j=1; j<=m; ++j)
        ans[p[j]] = j;
    Hungop+=m;
    return ans;
}

int MincostOp;

struct edge
{
    int to, cap,cost,flow;  // куда идет ребро, пропускная способность, стоимость, величина потока
    size_t back;    // откуда пришло ребро
};

void add_edge(vector<vector<edge>> &g, int from , int to, int cap, int cost)
{
    //cout << "from: " <<from << " to: " <<to << " cap: " << cap << " cost: "<< cost <<  endl;

    MincostOp+=5;
    edge e1 = {to,cap,cost,0,g[to].size()};

    MincostOp+=5;
    edge e2 = {from,0,-cost,0, g[from].size()};
    g[from].push_back(e1);
    g[to].push_back(e2);

    MincostOp+=2;

}
vector<int> mincostmaxflow(int sz, int **a)
{
    int s = 0;  // исток
    int t = sz+sz+1;// сток
    int nn = t+1;
    MincostOp+=3;
    vector<vector<edge>> g(nn);
    MincostOp+=nn;

    // добавили ребра из истока в работников
    // добавили ребра из задач в сток
    MincostOp+=sz;
    for (int i = 1; i<=sz; i++)
    {

        add_edge(g, s, i, 1, 0);
        add_edge(g, i+sz, t, 1, 0);
    }
    MincostOp+=sz*sz;
    for (int i = 1; i<=sz; i++)
    {
        for (int j = 1; j<=sz; j++)
        {
            add_edge(g, i, j+sz, 1, a[i][j]);
        }
    }
    int flow = 0, cost = 0;
    MincostOp+=2;
    while (flow<sz)
    {
        MincostOp++;
        vector<int> id(nn);
        vector<int> d(nn,INF);
        vector<int> q(nn);
        vector<int> p(nn);

        vector<size_t> p_rib(nn);

        MincostOp+=5*nn;
        int qh = 0, qt = 0;
        q[qt++] = s;
        d[s] = 0;
        MincostOp+=5;
        while (qh!=qt)
        {
            MincostOp+=2;
            int v = q[qh++];
            MincostOp++;
            id[v] = 2;
            MincostOp++;
            if (qh==nn)
            {
                MincostOp++;
                qh = 0;
            }
            for (int i = 0; i<g[v].size(); i++)
            {
                MincostOp++;
                edge &e = g[v][i];
                MincostOp+=3;
                if (e.flow < e.cap && d[v] + e.cost < d[e.to]) {
                    MincostOp+=2;
                    d[e.to] = d[v] + e.cost;
                    MincostOp++;
                    if (id[e.to] == 0) {
                        MincostOp+=2;
                        q[qt++] = e.to;
                        MincostOp++;
                        if (qt == nn)
                        {
                            MincostOp++;
                            qt = 0;
                        }
                    }
                    else if (id[e.to] == 2) {
                        MincostOp++;
                        if (--qh == -1)
                        {
                            MincostOp++;
                            qh = nn-1;
                        }
                        MincostOp++;
                        q[qh] = e.to;
                    }
                    id[e.to] = 1;
                    p[e.to] = v;
                    p_rib[e.to] = i;
                    MincostOp+=3;
                }
            }
        }
        MincostOp++;
        if (d[t]==INF)
            break;
        MincostOp++;
        int addflow = sz-flow;
        for (int v=t; v!=s; v=p[v]) {
            MincostOp++;
            int pv = p[v];
            size_t pr = p_rib[v];
            MincostOp++;
            addflow = min (addflow, g[pv][pr].cap - g[pv][pr].flow);
        }
        for (int v=t; v!=s; v=p[v]) {
            MincostOp++;
            int pv = p[v];
            MincostOp+=2;
            size_t pr = p_rib[v],  r = g[pv][pr].back;
            MincostOp++;
            g[pv][pr].flow += addflow;
            MincostOp++;
            g[v][r].flow -= addflow;
            MincostOp++;
            cost += g[pv][pr].cost * addflow;
        }
        MincostOp++;
        flow += addflow;

    }
    vector<int> ans(sz+1);
    MincostOp+=sz+1;
    for (int i = 1; i<=sz; i++)
    {
        MincostOp++;
        for (int j = 0; j<g[i].size(); j++)
        {
            MincostOp++;
            if (g[i][j].flow==1)
            {
                MincostOp++;
                ans[i] = j;
            }
        }
    }
    return ans;

}
void solve(ostream &cout)
{

    MincostOp= 0;
    Hungop = 0;
    // венгерский алгоритм

    auto ans1 = HungarianAlgo(n, a);
    auto ans2 = mincostmaxflow(n, a);

    int cost = 0;
    for (int i = 1; i<=n; i++)
    {
        cost +=a[i][ans1[i]];
        cout << ans1[i] << " ";
    }


    cout <<"Минимальные затраты: " << cost  <<endl;
    cout << "Количество операций венгерского алгоритма: " << Hungop << "\n";
    cout << "Количество операций потокового алгоритма: " << MincostOp << "\n";



}
int get_command()
{
    int x = -1;
    while (x<0 || x>3)
    {
        cout << "Введите 1 для проведения иследование\n        2 для ввода данных с файла\n        3 для ввода данных вручную\n        0 для выхода\n";
        cin >> x;
    }
    return x;
}
void issledovanie()
{
    int MAXTEST = 10;   // это изменять чтоб увеличить количество тестов
    n = 25; //это изменять чтоб увеличить размер таблицы
    a = new int*[n+1];
    for (int i = 0; i<=n; i++)
        a[i] = new int[n+1];
    int mod = 10;
    ofstream cout("issledovanie.txt");
    for (int i = 0; i<MAXTEST; i++)
    {
        for (int j = 0; j<=n; j++)
            for (int k = 0; k<=n; k++)
                a[j][k] = 0;
        for (int j = 1; j<=n; j++)
        {
            for (int k = 1; k<=n; k++)
            {
                a[j][k] = rand()%mod+1;
                cout << a[j][k] << " "; // это закомментить чтоб не выводилась матрица в файл
            }
            cout << endl;    //это закомментить чтоб не выводилась матрица в файл
        }
        solve(cout);
    }
    cout.close();
}
int main()
{

    while (true)
    {
        int x = get_command();
        if (x == 0)
            break;
        if (x == 1)
        {
            issledovanie();
        }
        else
        if (x == 2)
        {
            bool readed = readfromfile();
            if (!readed)
            {
                cout << "Неправильный путь или неверные входные данные в файле. Повторите еще раз";
                continue;
            }
            solve(cout);
        }
        else
            if (x == 3)
            {
                read();
                solve(cout);
            }
    }
}