// Транспортная.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include #include #include #include #include #include #include #include #include #include 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> &path, int M, int N, int line, int column, int newI, int newJ); bool SearchInColumn(int **x, list> &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>path; path.push_back(make_pair(newI, newJ)); if (!SearchInLine(x, path, M, N, newI, newJ, newI, newJ)) return false; list>::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]> 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> &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> &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; } }