// Транспортная.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include <iostream>
#include <locale.h>
#include <malloc.h>
#include <time.h>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <clocale>
#include <list>
using namespace std;
void Print(int **rez, int *a, int M, int *b, int N,wchar_t aw,wchar_t bw,const wchar_t *mess)
{
wprintf(mess);
int i, j;
for (i = 1; i <= N; i++)
wprintf(L"\t%c(%3.d)", bw, b[i]);
cout << "\n";
for (i = 1; i <= M; i++)
{
wprintf(L"%c(%3.d)", aw, a[i]);
for (int j = 1; j <= N; j++)
{
wprintf(L"\t%3.d", rez[i][j]);
}
wprintf(L"\n");
}
wprintf(L"\n");
}
bool Check(int &M,int &N, int *a,int *b,int **C, int **x)
{
int sumA = 0, sumB = 0;
bool closed = true;
for (int i = 1; i <= M; i++){
sumA += a[i];
}
for (int i = 1; i <= N; i++){
sumB += b[i];
}
if (sumA==sumB)
cout<<"Задача закрытая\n";
else
{
closed = false;
cout<<"Задача открытая\n";
if (sumA > sumB)
{
cout<<"Введен фиктивный потребитель\n";
N++;
b[N] = sumA - sumB;
}
else
{
cout<<"Введен фиктивный поставщик\n";
M++;
a[M] = sumB - sumA;
}
}
return closed;
}
int Cost(int M, int N, int **Rez, int **C)
{
int S = 0;
for (int i = 1; i <= M; i++)
for (int j = 1; j <= N; j++)
if (Rez[i][j] > 0)
S += Rez[i][j] * C[i][j];
return S;
}
void NorthWest(int M, int N, int *A, int *B, int **Rez)
{
int i, j;
int *a1, *b1;
a1 = (int*)malloc(M*sizeof(int));
b1 = (int*)malloc(N*sizeof(int));
for (i = 1; i <= M; i++)
a1[i] = A[i];
for (i = 1; i <= N; i++)
b1[i] = B[i];
i = 1; j = 1;
while (i <= M && j <= N)
{
if (a1[i] >= b1[j])
{
Rez[i][j] = b1[j];
a1[i] -= b1[j];
j++;
}
else
{
Rez[i][j] = a1[i];
b1[j] -= a1[i];
i++;
}
}
}
void MinCost(int M, int N, int *a, int *b, int** C, int **rez)
{
int *a1 = (int*)malloc(M*sizeof(int));
for (int i = 1; i <= M; i++)
a1[i] = a[i];
int *b1 = (int*)malloc(N*sizeof(int));
for (int i = 1; i <= N; i++)
b1[i] = b[i];
int minI, minJ;
bool flag = true;
bool *I = (bool*)calloc(M, sizeof(bool));
for (int i = 1; i <= M; i++)
I[i] = false;
bool *J = (bool*)calloc(N, sizeof(bool));
for (int i = 1; i <= N; i++)
J[i] = false;
while (flag)
{
flag = false;
for (int i = 1; i <= M; i++)
if (!I[i])
{
minI = i;
break;
}
for (int i = 1; i <= N; i++)
if (!J[i])
{
minJ = i;
break;
}
for (int i = 1; i <= M; i++)
{
for (int j = 1; j <= N; j++)
{
if (C[minI][minJ] >= C[i][j] && !I[i] && !J[j])
{
minI = i;
minJ = j;
flag = true;
}
}
}
if (!flag && !C[minI][minJ] && !I[minI] && !J[minJ])
flag = true;
if (flag)
{
if (a1[minI] > b1[minJ])
{
rez[minI][minJ] = b1[minJ];
a1[minI] -= b1[minJ];
J[minJ] = true;
}
else
{
rez[minI][minJ] = a1[minI];
b1[minJ] -= a1[minI];
I[minI] = true;
}
}
}
}
int min(int a, int b)
{
if (a < b)
return a;
else
return b;
}
bool SearchInLine(int **x, list<pair<int, int>> &path, int M, int N, int line, int column, int newI, int newJ);
bool SearchInColumn(int **x, list<pair<int, int>> &path, int M, int N, int line, int column, int newI, int NewJ);
void GetPotentialInLine(int* u, int *v, int line, int M, int N, int **x, int **C, bool *found);
void GetPotentialInColumn(int* u, int *v, int column, int M, int N, int **x, int **C, bool *found);
bool Optimaze(int ** x, int M, int N, int newI, int newJ)
{
list<pair<int, int>>path;
path.push_back(make_pair(newI, newJ));
if (!SearchInLine(x, path, M, N, newI, newJ, newI, newJ))
return false;
list<pair<int, int>>::iterator it;
int sign = 1;
int minimal = 0;
for (it = path.begin(); it != path.end(); it++)
if (++sign % 2)
if (!minimal)
minimal = x[it->first][it->second];
else
if (minimal > x[it->first][it->second])
minimal = x[it->first][it->second];
for (it = path.begin(); it != path.end(); it++)
if (++sign % 2)
x[it->first][it->second] -= minimal;
else
x[it->first][it->second] += minimal;
path.clear();
return true;
}
void Solution(int M, int N, int *A, int *B, int **C,int **Rez)
{
int i, j;
int *u = (int*)malloc(M*sizeof(int));
int *v = (int*)malloc(N*sizeof(int));
bool *found = (bool*)malloc((M + N)*sizeof(bool));
int im, jm;
bool optima, needMin;
int tMin;
while (true)
{
tMin = 1000;
optima = true;
needMin = false;
for (int i = 1; i <= M; i++)
{
u[i] = 0;
found[i] = false;
}
for (int j = 1; j <= N; j++)
{
v[j] = 0;
found[M + j] = false;
}
GetPotentialInLine(u, v, 1, M, N, Rez, C, found);
Print(Rez, u, M, v, N,'u','v',L"Новая таблица\n");
for (i = 1; i <= M; i++)
for (j = 1; j <= N; j++)
if (C[i][j]-u[i]-v[j]<0)
{
optima = false;
if (C[i][j] - u[i] - v[j]<tMin)
{
tMin = C[i][j]-u[i]-v[j];
im = i;
jm = j;
needMin = true;
}
}
if (!optima)
{
cout << "Решение неоптимальное\n\n";
if (Optimaze(Rez,M,N,im,jm))
cout << "Общая стоимость:" << Cost(M, N, Rez, C)<<"\n";
else
{
cout << "Ошибка\n";
optima = true;
}
}
else
cout << "Решение оптимальное\n\n";
if (optima)
break;
}
}
void Random(int M, int N, int maxNum)
{
int *a, *b, **x, **c;
int lastASize = M,vibor;
a = (int*)calloc(M + 1, sizeof(int));
b = (int*)calloc(N + 1, sizeof(int));
x = (int**)calloc(M + 1, sizeof(double*));
c = (int**)calloc(M + 1, sizeof(double*));
srand(time(NULL));
for (int i = 1; i <= M; i++)
{
a[i] = rand() % maxNum + 10;
x[i] = (int*)calloc(N + 1, sizeof(int));
c[i] = (int*)calloc(N + 1, sizeof(int));
for (int j = 1; j <= N; j++)
{
b[j] = rand() % maxNum + 10;
c[i][j] = rand() % maxNum + 10;
}
}
x[M] = (int*)calloc(N + 1, sizeof(int));
c[M] = (int*)calloc(N + 1, sizeof(int));
if (!Check(M, N, a, b, c, x))
Print(c, a, M, b, N, 'a', 'b', L"Новая таблица:\n");
cout << "1-метод северо-западного угла;\n2-метод минимальных стоимостей;\n";
cin >> vibor;
switch (vibor)
{
case 1:
NorthWest(M, N, a, b, x);
cout << "Общая стоимость по методу северо-западного угла:";
break;
case 2:
MinCost(M, N, a, b, c, x);
cout << "Общая стоимость по методу минимальных стоимостей:";
break;
default:
break;
}
cout<< Cost(M, N, x, c) << "\n";
Solution(M, N, a, b, c, x);
}
bool SearchInLine(int **x, std::list<std::pair<int, int>> &path, int M, int N, int line, int column, int newI, int newJ){
for (int j = 1; j <= N; j++){
if (j != column && x[line][j] > 0){
if (j == newJ){
path.push_back(make_pair(line, j));
return true;
}
if (SearchInColumn(x, path, M, N, line, j, newI, newJ)){
path.push_back(make_pair(line, j));
return true;
}
}
}
return false;
}
void GetPotentialInLine(int* u, int *v, int line, int M, int N, int **x, int **C, bool *found)
{
for (int i = 1; i <= N; i++)
if (x[line][i] > 0 && !v[i] && !found[M + i])
{
v[i] = C[line][i] - u[line];
found[M + i] = true;
GetPotentialInColumn(u, v, i, M, N, x, C, found);
}
}
void GetPotentialInColumn(int* u, int *v, int column, int M, int N, int **x, int **C, bool *found)
{
for (int i = 1; i <= M; i++)
if (x[i][column] > 0 && !u[i] && !found[i])
{
u[i] = C[i][column] - v[column];
found[i] = true;
GetPotentialInLine(u, v, i, M, N, x, C, found);
}
}
bool SearchInColumn(int **x, std::list<std::pair<int, int>> &path, int M, int N, int line, int column, int newI, int newJ){
for (int i = 1; i <= M; i++){
if (i != line && x[i][column] > 0){
if (SearchInLine(x, path, M, N, i, column, newI, newJ)){
path.push_back(make_pair(i, column));
return true;
}
}
}
return false;
}
int main()
{
int vibor;
setlocale(LC_ALL, "rus");
srand(time(NULL));
int i, j, m = 3, n = 5, *a, *b, **c, A = 0, B = 0, **rez,Max;
a = (int*)malloc(m*sizeof(int));
b = (int*)malloc(n*sizeof(int));
c = (int**)malloc(m*sizeof(int*));
for (i = 1; i <= m; i++)
c[i] = (int*)malloc(n*sizeof(int));
rez = (int**)malloc(m*sizeof(int*));
for (i = 1; i <= m; i++)
rez[i] = (int*)malloc(n*sizeof(int));
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
rez[i][j] = 0;
cout << "1-задание из курсовой;\n2-рандом;\n";
cin >> vibor;
switch (vibor)
{
case 1:
a[1] = 300;
a[2] = 150;
a[3] = 250;
b[1] = 170;
b[2] = 110;
b[3] = 100;
b[4] = 120;
b[5] = 200;
c[1][1] = 70;
c[1][2] = 50;
c[1][3] = 15;
c[1][4] = 80;
c[1][5] = 70;
c[2][1] = 80;
c[2][2] = 90;
c[2][3] = 40;
c[2][4] = 60;
c[2][5] = 85;
c[3][1] = 50;
c[3][2] = 10;
c[3][3] = 90;
c[3][4] = 11;
c[3][5] = 25;
Print(c, a, m, b, n, 'a', 'b', L"\nТаблица\n");
cout << "\n";
cout << "1-метод северо-западного угла;\n2-метод минимальных стоимостей;\n";
cin >> vibor;
switch (vibor)
{
case 1:
NorthWest(m, n, a, b, rez);
cout << "Общая стоимость по методу северо-западного угла:" << Cost(m, n, rez, c) << "\n";
Solution(m, n, a, b, c, rez);
break;
case 2:
MinCost(m, n, a, b, c, rez);
cout << "Общая стоимость по методу минимальных стоимостей:" << Cost(m, n, rez, c) << "\n";
Solution(m, n, a, b, c, rez);
break;
default:
break;
}
return 0;
case 2:
cin>>m;
cin >> n;
cin >> Max;
Random(m, n, Max);
default:
break;
}
}