include iostream include cstdlib include cstdio include ctime define A

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#define A_SIZE 3
#define B_SIZE 5
#define MAX_NUM 100

void PrintPlan(std::wstring message, int **X, int *A, int *B, int aSize, int bSize){
    std::wcout << message;
    for(int i = 0; i < bSize; i++){
        printf("\tB[%i]", B[i]);
    }
    printf("\n");
    for(int i = 0; i < aSize; i++){
        printf("A[%i]:", A[i]);
        for(int j = 0; j < bSize; j++){
            printf("\t%i", X[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void PrintPoint(std::wstring message, int *A, char point,int aSize){
    std::wcout << message;
    for(int i = 0; i < aSize; i++){
        printf("%c[%i]: %i\n", point, i, A[i]);
    }
    printf("\n");
}

int NorthwestCornerMethod(int* A1, int aSize, int* B1, int bSize, int** X, int** C){
    int *A = (int*)malloc(aSize*sizeof(int));
    for(int i = 0; i < aSize; i++){
        A[i] = A1[i];
    }
    int *B = (int*)malloc(bSize*sizeof(int));
    for(int i = 0; i < bSize; i++){
        B[i] = B1[i];
    }
    int aIndex = 0, bIndex = 0, sum = 0;
    while(aIndex < aSize && bIndex < bSize){
        if(A[aIndex] > B[bIndex]){
            X[aIndex][bIndex] = B[bIndex];
            A[aIndex] -= B[bIndex];
            sum += C[aIndex][bIndex]*X[aIndex][bIndex];
            bIndex++;
        }
        else{
            X[aIndex][bIndex] = A[aIndex];
            B[bIndex] -= A[aIndex];
            sum += C[aIndex][bIndex]*X[aIndex][bIndex];
            aIndex++;
        }
    }
    free(A);
    free(B);
    return sum;
}

int MinimalPricesMethod(int* A1, int aSize, int* B1, int bSize, int** X, int** C){
    int *A = (int*)malloc(aSize*sizeof(int));
    for(int i = 0; i < aSize; i++){
        A[i] = A1[i];
    }
    int *B = (int*)malloc(bSize*sizeof(int));
    for(int i = 0; i < bSize; i++){
        B[i] = B1[i];
    }
    int sum = 0, minI, minJ;
    bool result = true;
    bool *usedI = (bool*)calloc(aSize, sizeof(bool));
    bool *usedJ = (bool*)calloc(bSize, sizeof(bool));
    while(result){
        result = false;
        for(int i = 0; i < aSize; i++){
            if(!usedI[i]){
                minI = i;
                break;
            }
        }
        for(int i = 0; i < bSize; i++){
            if(!usedJ[i]){
                minJ = i;
                break;
            }
        }
        for(int i = 0; i < aSize; i++){
            for(int j = 0; j < bSize; j++){
                if(C[minI][minJ] >= C[i][j] && !usedI[i] && !usedJ[j]){
                    minI = i;
                    minJ = j;
                    result = true;
                }
            }
        }
        if(result){
            if(A[minI] > B[minJ]){
                X[minI][minJ] = B[minJ];
                A[minI] -= B[minJ];
                sum += C[minI][minJ]*X[minI][minJ];
                usedJ[minJ] = true;
            }
            else{
                X[minI][minJ] = A[minI];
                B[minJ] -= A[minI];
                sum += C[minI][minJ]*X[minI][minJ];
                usedI[minI] = true;
            }
        }
    }
    free(A);
    free(B);
    free(usedI);
    free(usedJ);
    return sum;
}

void MakeRandomTask(int aSize, int bSize, int maxNum){
    int *A, *B, **X, **C;
    A = (int*)malloc(aSize*sizeof(int));
    B = (int*)malloc(bSize*sizeof(int));
    X = (int**)malloc(aSize*sizeof(int*));
    C = (int**)malloc(aSize*sizeof(int*));
    srand(time(NULL));
    for(int i = 0; i < aSize; i++){
        A[i] = rand()%maxNum;
        X[i] = (int*)calloc(bSize, sizeof(int));
        C[i] = (int*)calloc(bSize, sizeof(int));
        for(int j = 0; j < bSize; j++){
            if(!i){
                B[j] = rand()%maxNum;
            }
            C[i][j] = rand()%maxNum;
        }
    }
    //PrintPoint(L"Пункты отправления:\n", A, 'A', aSize);
    //PrintPoint(L"Пункты назначения:\n", B, 'B', bSize);
    PrintPlan(L"\t\tСтоимость перевозок\n", C, A, B, aSize, bSize);
    int sum = NorthwestCornerMethod(A, aSize, B, bSize, X, C);
    PrintPlan(L"Метод северо-западного угла:\n\t\tПлан перевозок\n", X, A, B, aSize, bSize);
    std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
    for(int i = 0; i < aSize; i++){
        for(int j = 0; j < bSize; j++){
            X[i][j] = 0;
        }
    }
    sum = MinimalPricesMethod(A, aSize, B, bSize, X, C);
    PrintPlan(L"\nМетод минимальных стоимостей:\n\t\tПлан перевозок\n", X, A, B, aSize, bSize);
    std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
    for(int i = 0; i < aSize; i++){
        free(X[i]);
        free(C[i]);
    }
    free(A);
    free(B);
    free(X);
    free(C);
}

void MakeKnownTask(){
    int *A, *B, **X, **C;
    A = (int*)malloc(3*sizeof(int));
    B = (int*)malloc(5*sizeof(int));
    X = (int**)malloc(3*sizeof(int*));
    C = (int**)malloc(3*sizeof(int*));
    for(int i = 0; i < 3; i++){
        X[i] = (int*)calloc(5, sizeof(int));
        C[i] = (int*)calloc(5, sizeof(int));
    }
    A[0] = 300;
    A[1] = 150;
    A[2] = 250;
    B[0] = 170;
    B[1] = 110;
    B[2] = 100;
    B[3] = 120;
    B[4] = 200;
    C[0][0] = 70;
    C[0][1] = 50;
    C[0][2] = 15;
    C[0][3] = 80;
    C[0][4] = 70;
    C[1][0] = 80;
    C[1][1] = 90;
    C[1][2] = 40;
    C[1][3] = 60;
    C[1][4] = 85;
    C[2][0] = 50;
    C[2][1] = 10;
    C[2][2] = 90;
    C[2][3] = 11;
    C[2][4] = 25;
    //PrintPoint(L"Пункты отправления:\n", A, 'A', 3);
    //PrintPoint(L"Пункты назначения:\n", B, 'B', 5);
    PrintPlan(L"\t\tСтоимость перевозок\n", C, A, B, 3, 5);
    int sum = NorthwestCornerMethod(A, 3, B, 5, X, C);
    PrintPlan(L"Метод северо-западного угла:\n\t\tПлан перевозок\n", X, A, B, 3, 5);
    std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 5; j++){
            X[i][j] = 0;
        }
    }
    sum = MinimalPricesMethod(A, 3, B, 5, X, C);
    PrintPlan(L"\nМетод минимальных стоимостей:\n\t\tПлан перевозок\n", X, A, B, 3, 5);
    std::wcout << L"Общий объем перевозок в тонно-километрах: " << sum << std::endl;
    for(int i = 0; i < 3; i++){
        free(X[i]);
        free(C[i]);
    }
    free(A);
    free(B);
    free(X);
    free(C);
}

using namespace std;

int main()
{
    setlocale(LC_ALL, ".866");
    MakeKnownTask();
    //MakeRandomTask(A_SIZE, B_SIZE, MAX_NUM);
    return 0;
}