6

#include <stdio.h>
#include <algorithm>
#include <limits.h>
#include <iostream>

using namespace std;

const int n = 3, m = 5;
int a[n], alfa[n];
int b[m], beta[m];
int x[n][m], c[n][m], delta[n][m];
bool zapol[n][m];
int rez;

int znaki[n][m];
int kol_v_stroke[n];
int kol_v_stolbce[m];
bool zapol1[n][m];
int sv_i, sv_j, i_tek, j_tek;

void Print() {
    for (int i = 0; i < n; i++) {
        printf("\n");
        for (int j = 0; j < m; j++)
            printf("%8d", x[i][j]);
        printf("%8d", a[i]);
    }
    printf("\n");
    for (int j = 0; j < m; j++)
        printf("%8d", b[j]);
    printf("\n");
}

void ser_zap(int a[n], int b[m], int c[n][m]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (b[j] != 0) {
                c[i][j] = min(a[i], b[j]);
                zapol[i][j] = true;
                a[i] = a[i] - c[i][j];
                b[j] = b[j] - c[i][j];
                if (a[i] == 0)
                    break;
            }
        }
    }
}

void Potencial() {
    for (int i = 0; i < n; i++)
        alfa[i] = -INT_MAX;
    for (int j = 0; j < m; j++)
        beta[j] = -INT_MAX;
    alfa[0] = 0;
    bool f;

    do {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (zapol[i][j]) {
                    if ((alfa[i] == -INT_MAX) && (beta[j] != -INT_MAX))
                        alfa[i] = c[i][j] - beta[j];
                    else
                        if ((alfa[i] != -INT_MAX) && (beta[j] == -INT_MAX))
                            beta[j] = c[i][j] - alfa[i];
                }
            }
        }
        f = false;
        for (int i = 0; i < n; i++)
            if (alfa[i] == -INT_MAX)
                f = true;
        for (int j = 0; j < m; j++)
            if (beta[j] == -INT_MAX)
                f = true;
    } while (f);
}

void Ozenka() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!(zapol[i][j]))
                delta[i][j] = beta[j] + alfa[i] - c[i][j];
            else
                delta[i][j] = 0;
        }
    }
}

bool optim() {
    bool f = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            if (!(zapol[i][j]) && (delta[i][j] > 0))
                f = false;
    }
    return f;
}

void Init_cicl() {

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) znaki[i][j] = 0;

    for (int i = 0; i < n; ++i)
        kol_v_stroke[i] = 0;
    for (int j = 0; j < m; ++j)
        kol_v_stolbce[j] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (zapol1[i][j]) {
                kol_v_stroke[i]++;
                kol_v_stolbce[j]++;
            }
        }
    }
    i_tek = sv_i;
    j_tek = sv_j;
    znaki[i_tek][j_tek] = 1;
}

void NewPlan() {
//  bool zapol1[n][m];
    int i_min, j_min, vmax, vmin;
    vmax = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (delta[i][j] > vmax && !(zapol[i][j])) {
                vmax = delta[i][j];
                sv_i = i;
                sv_j = j;
            }
        }
    }
    if (vmax == 0) return;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            zapol1[i][j] = zapol[i][j];
    Init_cicl();
    do {
        for (int i = 0; i < n; ++i) {
            if (i != i_tek && zapol1[i][j_tek]) {
                i_tek = i;
                znaki[i_tek][j_tek] = -1;
                break;
            }
        }
        if (i_tek == sv_i)  break;
        for (int j = 0; j < m; ++j) {
            if ((j != j_tek) && (zapol1[i_tek][j])) {
                j_tek = j;
                znaki[i_tek][j_tek] = 1;
                break;
            }
        }
        if (kol_v_stolbce[j_tek] < 2) {
            zapol1[i_tek][j_tek] = false;
            Init_cicl();
        }
        if (kol_v_stroke[i_tek] < 2) {
            zapol1[i_tek][j_tek] = false;
            Init_cicl();
        }
    } while (true);

    vmin = INT_MAX;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (znaki[i][j] == -1 && x[i][j] < vmin) {
                vmin = x[i][j];
                i_min = i;
                j_min = j;
            }
        }
    }

    zapol[i_min][j_min] = false;
    zapol[sv_i][sv_j] = true;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            x[i][j] += znaki[i][j] * vmin;


}

int main(void) {
    a[0] = 280; a[1] = 350; a[2] = 250;
    b[0] = 130; b[1] = 100; b[2] = 300; b[3] = 270; b[4] = 80;
    c[0][0] = 13; c[0][1] = 8; c[0][2] = 10; c[0][3] = 9; c[0][4] = 6;
    c[1][0] = 12; c[1][1] = 9; c[1][2] = 11; c[1][3] = 5; c[1][4] = 8;
    c[2][0] = 14; c[2][1] = 7; c[2][2] = 10; c[2][3] = 14; c[2][4] = 9;
    ser_zap(a, b, x);
    int t;
    Print();
    do {
        Print();
        Potencial();
        Ozenka();
        NewPlan();
        Print();
    } while (!optim());
    printf("YES!!!!!!");
    Print();
    rez = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            rez += x[i][j] * c[i][j];
    printf("%d\n", rez);
    return 0;
}