fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <iomanip>
  5. #include <algorithm>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10. const int INF = 9999;
  11. using Matrix = vector<vector<int>>;
  12.  
  13. int reduceRows(Matrix& mat) {
  14.     int reduction = 0;
  15.     for (auto& row : mat) {
  16.         int minVal = *min_element(row.begin(), row.end());
  17.         if (minVal != INF && minVal > 0) {
  18.             for (auto& val : row) {
  19.                 if (val != INF) val -= minVal;
  20.             }
  21.             reduction += minVal;
  22.         }
  23.     }
  24.     return reduction;
  25. }
  26.  
  27. int reduceCols(Matrix& mat) {
  28.     int reduction = 0;
  29.     int n = mat.size();
  30.     for (int col = 0; col < n; ++col) {
  31.         int minVal = INF;
  32.         for (int row = 0; row < n; ++row) {
  33.             minVal = min(minVal, mat[row][col]);
  34.         }
  35.         if (minVal != INF && minVal > 0) {
  36.             for (int row = 0; row < n; ++row) {
  37.                 if (mat[row][col] != INF)
  38.                     mat[row][col] -= minVal;
  39.             }
  40.             reduction += minVal;
  41.         }
  42.     }
  43.     return reduction;
  44. }
  45.  
  46. void printMatrix(const Matrix& mat) {
  47.     cout << "    ";
  48.     for (int i = 0; i < mat.size(); ++i)
  49.         cout << setw(4) << (i + 1);
  50.     cout << "\n";
  51.     for (int i = 0; i < mat.size(); ++i) {
  52.         cout << setw(4) << (i + 1);
  53.         for (int j = 0; j < mat[i].size(); ++j) {
  54.             if (mat[i][j] == INF)
  55.                 cout << setw(4) << "M";
  56.             else
  57.                 cout << setw(4) << mat[i][j];
  58.         }
  59.         cout << "\n";
  60.     }
  61. }
  62.  
  63. pair<int, pair<int, int>> selectNextEdge(const Matrix& mat) {
  64.     int maxPenalty = -1;
  65.     pair<int, int> bestEdge = {-1, -1};
  66.  
  67.     for (int i = 0; i < mat.size(); ++i) {
  68.         for (int j = 0; j < mat[i].size(); ++j) {
  69.             if (mat[i][j] == 0) {
  70.                 int rowMin = INF, colMin = INF;
  71.                 for (int k = 0; k < mat.size(); ++k) {
  72.                     if (k != j)
  73.                         rowMin = min(rowMin, mat[i][k]);
  74.                     if (k != i)
  75.                         colMin = min(colMin, mat[k][j]);
  76.                 }
  77.                 int penalty = (rowMin == INF ? 0 : rowMin) + (colMin == INF ? 0 : colMin);
  78.                 if (penalty > maxPenalty) {
  79.                     maxPenalty = penalty;
  80.                     bestEdge = {i, j};
  81.                 }
  82.             }
  83.         }
  84.     }
  85.     return {maxPenalty, bestEdge};
  86. }
  87.  
  88. int calculateUpperBound(const Matrix& mat) {
  89.     Matrix temp = mat;
  90.     int red1 = reduceRows(temp);
  91.     int red2 = reduceCols(temp);
  92.     return red1 + red2;
  93. }
  94.  
  95. int main() {
  96.     const int N = 5;
  97.     Matrix cost = {
  98.         {INF, 100,  220,  150,  210},
  99.         {120, INF, 80,  120,  130},
  100.         {220,  110,  INF, 160,  185},
  101.         {150,  110,  160,  INF, 190},
  102.         {210,  130,  185,  190,  INF}
  103.     };
  104.  
  105.     Matrix current = cost;
  106.     vector<pair<int, int>> path;
  107.     int totalCost = 0;
  108.     int level = 0;
  109.  
  110.     while (path.size() < N) {
  111.         cout << "\nІтерація " << level + 1 << ":\n";
  112.  
  113.         int upperBound = calculateUpperBound(current);
  114.         cout << "Верхня межа (жадібна оцінка): " << (upperBound >= INF ? -1 : upperBound) << "\n";
  115.  
  116.         int tempZ = totalCost;
  117.         Matrix temp = current;
  118.         int red1 = reduceRows(temp);
  119.         int red2 = reduceCols(temp);
  120.         int Z = totalCost + red1 + red2;
  121.  
  122.         cout << "Z перед викресленням: " << tempZ << "\n";
  123.         cout << "Редукція по рядках: " << red1 << ", по стовпцях: " << red2 << "\n";
  124.         cout << "Z після редукції: " << Z << "\n";
  125.         cout << "Матриця після редукції:\n";
  126.         printMatrix(temp);
  127.  
  128.         auto [penalty, edge] = selectNextEdge(temp);
  129.         int i = edge.first;
  130.         int j = edge.second;
  131.  
  132.         if (i == -1 || j == -1) {
  133.             cout << "Немає допустимого ребра\n";
  134.             break;
  135.         }
  136.  
  137.         cout << "Вибрана дуга: " << (i + 1) << " → " << (j + 1) << "\n";
  138.  
  139.         path.push_back({i, j});
  140.         totalCost += cost[i][j];
  141.  
  142.         // Побудова часткового циклу
  143.         vector<pair<int, int>> tempPath = path;
  144.         sort(tempPath.begin(), tempPath.end());
  145.  
  146.         set<int> visited;
  147.         int start = tempPath[0].first;
  148.         vector<int> cycle;
  149.         cycle.push_back(start);
  150.         int currentNode = start;
  151.         bool hasCycle = false;
  152.  
  153.         while (true) {
  154.             auto it = find_if(tempPath.begin(), tempPath.end(),
  155.                 [currentNode](pair<int, int> p) { return p.first == currentNode; });
  156.             if (it == tempPath.end()) break;
  157.             int next = it->second;
  158.             if (visited.count(next)) break;
  159.             cycle.push_back(next);
  160.             if (next == start) {
  161.                 hasCycle = true;
  162.                 break;
  163.             }
  164.             visited.insert(currentNode);
  165.             currentNode = next;
  166.         }
  167.  
  168.         if (hasCycle) {
  169.             cout << "Цикл: ";
  170.             for (int k = 0; k < cycle.size(); ++k) {
  171.                 cout << cycle[k] + 1;
  172.                 if (k != cycle.size() - 1) cout << " → ";
  173.             }
  174.             cout << "\n";
  175.         }
  176.  
  177.         // Обновление матрицы
  178.         for (int k = 0; k < N; ++k) {
  179.             current[i][k] = INF;
  180.             current[k][j] = INF;
  181.         }
  182.         current[j][i] = INF;
  183.  
  184.         level++;
  185.     }
  186.  
  187.     cout << "\nЗагальна довжина маршруту (нижня межа): " << totalCost << "\n";
  188.     cout << "Шлях: ";
  189.     for (auto [from, to] : path) {
  190.         cout << from + 1 << " → " << to + 1 << ", ";
  191.     }
  192.     cout << "\n";
  193.  
  194.     return 0;
  195. }
  196.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Ітерація 1:
Верхня межа (жадібна оцінка): 660
Z перед викресленням: 0
Редукція по рядках: 530, по стовпцях: 130
Z після редукції: 660
Матриця після редукції:
       1   2   3   4   5
   1   M   0 120  10  60
   2   0   M   0   0   0
   3  70   0   M  10  25
   4   0   0  50   M  30
   5  40   0  55  20   M
Вибрана дуга: 2 → 3

Ітерація 2:
Верхня межа (жадібна оцінка): 565
Z перед викресленням: 80
Редукція по рядках: 500, по стовпцях: 65
Z після редукції: 645
Матриця після редукції:
       1   2   3   4   5
   1   M   0   M  50  85
   2   M   M   M   M   M
   3  20   M   M   0   0
   4   0   0   M   M  55
   5  40   0   M  60   M
Вибрана дуга: 3 → 5

Ітерація 3:
Верхня межа (жадібна оцінка): 430
Z перед викресленням: 265
Редукція по рядках: 340, по стовпцях: 90
Z після редукції: 695
Матриця після редукції:
       1   2   3   4   5
   1   M   0   M   0   M
   2   M   M   M   M   M
   3   M   M   M   M   M
   4   0   0   M   M   M
   5  40   0   M  10   M
Вибрана дуга: 4 → 1

Ітерація 4:
Верхня межа (жадібна оцінка): 290
Z перед викресленням: 415
Редукція по рядках: 230, по стовпцях: 60
Z після редукції: 705
Матриця після редукції:
       1   2   3   4   5
   1   M   0   M   M   M
   2   M   M   M   M   M
   3   M   M   M   M   M
   4   M   M   M   M   M
   5   M   0   M   0   M
Вибрана дуга: 1 → 2

Ітерація 5:
Верхня межа (жадібна оцінка): 190
Z перед викресленням: 515
Редукція по рядках: 190, по стовпцях: 0
Z після редукції: 705
Матриця після редукції:
       1   2   3   4   5
   1   M   M   M   M   M
   2   M   M   M   M   M
   3   M   M   M   M   M
   4   M   M   M   M   M
   5   M   M   M   0   M
Вибрана дуга: 5 → 4

Загальна довжина маршруту (нижня межа): 705
Шлях: 2 → 3, 3 → 5, 4 → 1, 1 → 2, 5 → 4,
https://ideone.com/jA5Cuk
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!