fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <iomanip>
  5. #include <string>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. const int N = 5; // количество городов
  10. const int INF = 1e6;
  11.  
  12. using Matrix = vector<vector<int>>;
  13.  
  14. void printMatrix(const Matrix& mat) {
  15.     for (int i = 0; i < N; ++i) {
  16.         for (int j = 0; j < N; ++j) {
  17.             if (mat[i][j] >= INF)
  18.                 cout << "M ";
  19.             else
  20.                 cout << setw(2) << mat[i][j] << " ";
  21.         }
  22.         cout << endl;
  23.     }
  24. }
  25.  
  26. int reduceRows(Matrix& mat) {
  27.     int reduction = 0;
  28.     for (int i = 0; i < N; ++i) {
  29.         int rowMin = INF;
  30.         for (int j = 0; j < N; ++j)
  31.             rowMin = min(rowMin, mat[i][j]);
  32.         if (rowMin == INF) continue;
  33.         for (int j = 0; j < N; ++j)
  34.             if (mat[i][j] < INF) mat[i][j] -= rowMin;
  35.         reduction += rowMin;
  36.     }
  37.     return reduction;
  38. }
  39.  
  40. int reduceCols(Matrix& mat) {
  41.     int reduction = 0;
  42.     for (int j = 0; j < N; ++j) {
  43.         int colMin = INF;
  44.         for (int i = 0; i < N; ++i)
  45.             colMin = min(colMin, mat[i][j]);
  46.         if (colMin == INF) continue;
  47.         for (int i = 0; i < N; ++i)
  48.             if (mat[i][j] < INF) mat[i][j] -= colMin;
  49.         reduction += colMin;
  50.     }
  51.     return reduction;
  52. }
  53.  
  54. pair<int, pair<int, int>> selectNextEdge(const Matrix& mat) {
  55.     int maxPenalty = -1;
  56.     pair<int, int> bestEdge = {-1, -1};
  57.  
  58.     for (int i = 0; i < N; ++i)
  59.         for (int j = 0; j < N; ++j)
  60.             if (mat[i][j] == 0) {
  61.                 int rowMin = INF, colMin = INF;
  62.                 for (int k = 0; k < N; ++k) {
  63.                     if (k != j) rowMin = min(rowMin, mat[i][k]);
  64.                     if (k != i) colMin = min(colMin, mat[k][j]);
  65.                 }
  66.                 int penalty = (rowMin == INF ? 0 : rowMin) + (colMin == INF ? 0 : colMin);
  67.                 if (penalty > maxPenalty) {
  68.                     maxPenalty = penalty;
  69.                     bestEdge = {i, j};
  70.                 }
  71.             }
  72.  
  73.     return {maxPenalty, bestEdge};
  74. }
  75.  
  76. int main() {
  77.     Matrix cost(N, vector<int>(N));
  78.     cout << "Введите матрицу " << N << "x" << N << " (используйте M для больших значений):\n";
  79.     for (int i = 0; i < N; ++i)
  80.         for (int j = 0; j < N; ++j) {
  81.             string s;
  82.             cin >> s;
  83.             if (s == "M" || s == "m")
  84.                 cost[i][j] = INF;
  85.             else
  86.                 cost[i][j] = stoi(s);
  87.         }
  88.  
  89.     vector<pair<int, int>> path;
  90.     vector<vector<bool>> visited(N, vector<bool>(N, false));
  91.     int totalCost = 0;
  92.     Matrix current = cost;
  93.     int level = 0;
  94.  
  95.     while (path.size() < N) {
  96.         cout << "\nИтерация " << level + 1 << ":\n";
  97.         Matrix temp = current;
  98.  
  99.         int red1 = reduceRows(temp);
  100.         int red2 = reduceCols(temp);
  101.         int Z = totalCost + red1 + red2;
  102.  
  103.         cout << "Матрица после редукции:\n";
  104.         printMatrix(temp);
  105.         cout << "Z = " << Z << " (накопленная нижняя граница)\n";
  106.  
  107.         auto [penalty, edge] = selectNextEdge(temp);
  108.         int i = edge.first;
  109.         int j = edge.second;
  110.  
  111.         if (i == -1 || j == -1) {
  112.             cout << "Нет подходящего ребра\n";
  113.             break;
  114.         }
  115.  
  116.         cout << "Выбрана дуга: " << char('A' + i) << " → " << char('A' + j) << "\n";
  117.  
  118.         path.push_back({i, j});
  119.         totalCost += cost[i][j];
  120.  
  121.         // Обновляем матрицу
  122.         for (int k = 0; k < N; ++k) {
  123.             current[i][k] = INF;
  124.             current[k][j] = INF;
  125.         }
  126.         current[j][i] = INF;
  127.  
  128.         level++;
  129.     }
  130.  
  131.     cout << "\nОптимальный путь:\n";
  132.     for (auto [from, to] : path) {
  133.         cout << char('A' + from) << " → " << char('A' + to) << "\n";
  134.     }
  135.     cout << "Общая стоимость пути: " << totalCost << "\n";
  136.  
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
M 100 220 150 210
120 M 80 120 130
220 110 M 160 185
150 110 160 M 190
210 130 185 190 M
stdout
copy 
Введите матрицу 5x5 (используйте M для больших значений):

Итерация 1:
Матрица после редукции:
M  0 120 10 60 
 0 M  0  0  0 
70  0 M 10 25 
 0  0 50 M 30 
40  0 55 20 M 
Z = 660 (накопленная нижняя граница)
Выбрана дуга: B → C

Итерация 2:
Матрица после редукции:
M  0 M 50 85 
M M M M M 
20 M M  0  0 
 0  0 M M 55 
40  0 M 60 M 
Z = 645 (накопленная нижняя граница)
Выбрана дуга: C → E

Итерация 3:
Матрица после редукции:
M  0 M  0 M 
M M M M M 
M M M M M 
 0  0 M M M 
40  0 M 10 M 
Z = 695 (накопленная нижняя граница)
Выбрана дуга: D → A

Итерация 4:
Матрица после редукции:
M  0 M M M 
M M M M M 
M M M M M 
M M M M M 
M  0 M  0 M 
Z = 705 (накопленная нижняя граница)
Выбрана дуга: A → B

Итерация 5:
Матрица после редукции:
M M M M M 
M M M M M 
M M M M M 
M M M M M 
M M M  0 M 
Z = 705 (накопленная нижняя граница)
Выбрана дуга: E → D

Оптимальный путь:
B → C
C → E
D → A
A → B
E → D
Общая стоимость пути: 705
https://ideone.com/esAGS7
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!