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

Поиск цикла на основе текущего пути:
Выбрана дуга: B → C
Частковий цикл: B → C

Итерация 2:
Верхняя граница (жадная оценка): -1
Z перед редукцией: 80
Редукция по строкам: 500
Редукция по столбцам: 65
Z = 80 + 500 + 65 = 645
Матрица после редукции:
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 

Поиск цикла на основе текущего пути:
Частковий цикл: B → C
Выбрана дуга: C → E
Частковий цикл: B → C → E

Итерация 3:
Верхняя граница (жадная оценка): -1
Z перед редукцией: 265
Редукция по строкам: 340
Редукция по столбцам: 90
Z = 265 + 340 + 90 = 695
Матрица после редукции:
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 

Поиск цикла на основе текущего пути:
Частковий цикл: B → C → E
Выбрана дуга: D → A
Частковий цикл: B → C → E
Частковий цикл: D → A

Итерация 4:
Верхняя граница (жадная оценка): -1
Z перед редукцией: 415
Редукция по строкам: 230
Редукция по столбцам: 60
Z = 415 + 230 + 60 = 705
Матрица после редукции:
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 

Поиск цикла на основе текущего пути:
Частковий цикл: B → C → E
Частковий цикл: D → A
Выбрана дуга: A → B
Частковий цикл: B → C → E
Частковий цикл: D → A

Итерация 5:
Верхняя граница (жадная оценка): -1
Z перед редукцией: 515
Редукция по строкам: 190
Редукция по столбцам: 0
Z = 515 + 190 + 0 = 705
Матрица после редукции:
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 

Поиск цикла на основе текущего пути:
Частковий цикл: B → C → E
Частковий цикл: D → A
Выбрана дуга: E → D
Частковий цикл: B → C → E → D → A → B

Оптимальный путь:
B → C
C → E
D → A
A → B
E → D
Общая стоимость пути: 705
https://ideone.com/jk8oaS
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!